Find maximum triplet in an array-CodePudding

I have an array of numbers [1,2,6,4,105,111,1024] I want to check all possible triplets a,b,c such that b%a ==0 and c%b ==0. For such triplets get the middle element b. Now I want to return the maximum possible b for such triplets.

For this array the valid triplets are :

indices:

(0,1,2) = middle item = 2
(0,1,3) = middle item = 2
(0,1,6) = middle item = 2
(0,3,6) = middle item = 4
(1,3,6) = middle item = 4

So the maximum value is 4 is the answer.

Here is my code:

int process(List<Integer> list) {
   int n = list.size();
   int max = -1;
   for(int i=0; i<n-2; i  ) {
    int a = list.get(i);
    boolean valid = true;
    for(int j=i 1; j<n-1; j  ) {
        int b = list.get(j);
        valid = b % a == 0;
        for(int k=j 1; valid && k<n; k  ) {
            int c = list.get(k);
            if(c % b ==0) {
                max = Math.max(max, b);
            }
        }
    }
    return max;
}

How to reduce the time complexity for this code.

constraints:

size of input list is 1 to 10^5. Each element in list is also 1 to 10^5

CodePudding user response：

c % b = 0 and b % a = 0 means a is the lowest factor OR a possible GCD of both b and c. However, since we need to find the maximum greatest value of the middle element, we will take a different route.

We put all the elements of the array in the hashMap with a boolean falsy value by default.
For each element in arr, we check with all it's factors by iterating till square root of this number.
If any of the factor exists already in the map, we perform one more check as to whether this factor has a factor of it's own present in the array. This way, the current factor at hand makes it the middle element of the triplet.
We keep taking maximum of those and return the answer. We return -1 if no such triplet exists.

Snippet:

import java.util.*;

public class Main {
    public static void main(String[] args) {
      int[] arr = {1,2,6,4,105,111,1024};
      System.out.println(solve(arr));
  }
  
  private static int solve(int[] arr){
    Map<Integer,Boolean> map = new HashMap<>();
    int max = -1;
    for(int i = 0 ; i < arr.length;   i){
      map.putIfAbsent(arr[i], false);
      boolean factorExists = false;
      
      for(int j = 1; j * j <= arr[i];   j){
        if(arr[i] % j == 0 && map.getOrDefault(j, false)){
          max = Math.max(max, j);
        }
        
        int cousin = arr[i] / j;
        if(arr[i] % j == 0 && arr[i] % cousin == 0 &&  map.getOrDefault(cousin, false)){
          max = Math.max(max, cousin);
        }
        
        factorExists = factorExists || map.containsKey(j) || map.containsKey(cousin);
      }
      
      map.put(arr[i], map.get(arr[i]) || factorExists);
    }
    
    return max;
  }
}

Time Complexity: O(n^1.5) since we walk through till square root of each element.

Space Complexity: O(n) since we store all the elements of the array in the map.

CodePudding user response：

Instead of using multiple for loops use single for loop and a HashMap to keep the modulo results for each position and with that you can do the same thing with O(n) time complexity