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

Check this C# solution:

-Loop through each element,

-loop and multiply each element with other elements,

-verify if the product exists in the array and is the max

private static int GetGreatest(int[] input)
    {
        int max = 0;        
        int p = 0; //product of pairs
         //loop through the input array
        for (int i = 0; i < input.Length; i++)
        {

            for (int j = i + 1; j < input.Length; j++)
            {
                p = input[i] * input[j];
                if (p > max && Array.IndexOf(input, p) != -1)
                {
                    max = p;
                }
            }
        }

        return max;
    }

Time complexity O(n^2)

Answer 2

Try this. Written in c++

#include <vector>
#include <algorithm>

using namespace std;

int MaxElement(vector< int > Input)
{
    sort(Input.begin(), Input.end());
    int LargestElementOfInput = 0;
    int i = 0;
    while (i < Input.size() - 1)
    {
        if (LargestElementOfInput == Input[Input.size() - (i + 1)])
        {
            i++;
            continue;
        }

        else
        {
            if (Input[i] != 0)
            {
                LargestElementOfInput = Input[Input.size() - (i + 1)];
                int AllowedValue = LargestElementOfInput / Input[i];
                int j = 0;

                while (j < Input.size())
                {
                    if (Input[j] > AllowedValue)
                        break;
                    else if (j == i)
                    {
                        j++;
                        continue;
                    }
                    else
                    {
                        int Product = Input[i] * Input[j++];
                        if (Product == LargestElementOfInput)
                            return Product;
                    }
                }
            }

            i++;
        }
    }

    return -1;
}

Answer 3

@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.

Answer 4

I came up with below solution where i am using one array list, and following one formula:

 divisor(a or b) X quotient(b or a) = dividend(c)

1. Sort the array.
2. Put array into Collection Col.(ex. which has faster lookup, and maintains insertion order)
3. Have 2 pointer a,c.
4. keep c at last, and a at 0.
5. try to follow (divisor(a or b) X quotient(b or a) = dividend(c)).
6. Check if a is divisor of c, if yes then check for b in col.(a
7. If a is divisor and list has b, then c is the answer. else increase a by 1, follow step 5, 6 till c-1.
8. if max not found then decrease c index, and follow the steps 4 and 5.

Answer 5

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 6

Efficient solution:

2 3 8 6

• Sort the array
• keep 3 pointers C, B and A.
• Keeping C at the last and A at 0 index and B at 1st index.
• traverse the array using pointers A and B till C and check if A*B=C exists or not.
  If it exists then C is your answer.
• Else, Move C a position back and traverse again keeping A at 0 and B at 1st index.

Keep repeating this till you get the sum or C reaches at 1st index.

Here's the complete solution:

int arr[] = new int[]{2, 3, 8, 6};
Arrays.sort(arr);

        int n=arr.length;
        int a,b,c,prod,max=-1;

        for(c=n-1;(c>1)&& (max==-1);c--){       // loop through C
            for(a=0;(a<c-1)&&(max==-1);a++){    // loop through A
                for(b=a+1;b<c;b++){             // loop through B
                    prod=arr[a]*arr[b];
                    if(prod==arr[c]){
                         System.out.println("A: "+arr[a]+" B: "+arr[b]);
                        max=arr[c];
                        break;
                    }
                    if(prod>arr[c]){ // no need to go further
                        break;
                    }
                }
            }
        }

System.out.println(max);

Answer 7

Once you have sorted the array, then you can use it to your advantage as below.

One improvement I can see - since you want to find the max element that meets the criteria,

1. Start from the right most element of the array. (8)
2. Divide that with the first element of the array. (8/2 = 4).
3. Now continue with the double pointer approach, till the element at second pointer is less than the value from the step 2 above or the match is found. (i.e., till second pointer value is < 4 or match is found).
4. If the match is found, then you got the max element.
5. Else, continue the loop with next highest element from the array. (6).