Maximum element in array which is equal to product of two elements in array

Question

We need to find the maximum element in an array which is also equal to product of two elements in the same array. For example [2,3,6,8] , here 6=2*3 so answer is 6.

My approach was to sort the array and followed by a two pointer method which checked whether the product exist for each element. This is o(nlog(n)) + O(n^2) = O(n^2) approach. Is there a faster way to this ?

Answer 1

There is a slight better solution with O(n * sqrt(n)) if you are allowed to use O(M) memory M = max number in A[i] Use an array of size M to mark every number while you traverse them from smaller to bigger number. For each number try all its factors and see if those were already present in the array map.

Here is a pseudo code for that:

#define M 1000000
int array_map[M+2];
int ans = -1;
sort(A,A+n);
for(i=0;i<n;i++) {
  for(j=1;j<=sqrt(A[i]);j++) {
    int num1 = j;
    if(A[i]%num1==0) {
      int num2 = A[i]/num1;
      if(array_map[num1] && array_map[num2]) {
        if(num1==num2) {
            if(array_map[num1]>=2) ans = A[i];
        } else {
          ans = A[i];
        }
      }
    }
  }
  array_map[A[i]]++;
}

There is an ever better approach if you know how to find all possible factors in log(M) this just becomes O(n*logM). You have to use sieve and backtracking for that

Answer 2

@JerryGoyal 's solution is correct. However, I think it can be optimized even further if instead of using B pointer, we use binary search to find the other factor of product if arr[c] is divisible by arr[a]. Here's the modification for his code:

for(c=n-1;(c>1)&& (max==-1);c--){       // loop through C
    for(a=0;(a<c-1)&&(max==-1);a++){    // loop through A
        if(arr[c]%arr[a]==0)            // If arr[c] is divisible by arr[a]
        {
            if(binary_search(a+1, c-1, (arr[c]/arr[a]))) //#include<algorithm>
            {
                max = arr[c];          // if the other factor x of arr[c]  is also in the array such that arr[c] = arr[a] * x
                break;
            }
        }
    }
}

I would have commented this on his solution, unfortunately I lack the reputation to do so.