Given an array A of N elements. The task is to find the greatest number S which is present in the array such that it is the product of two elements of a given array (S cannot be included in pair. Also, pair must be from different indices). If there is no such pair then print -1.
Table of Contents
Example
Input:
6 10 2 2 4 30 35
Output:
4
Brute force: Approach 1 for Find Pair with Greatest Product in Array
We can take every pair of numbers in the array and check if their product is present in the array or not and we among all these valid pairs, we will choose the one with the highest product.
Algorithm
- Sort the array in non-decreasing order.
- Initialize a variable “ans” with -1.
- Run a loop for I in range 0 to n-1
- Run a loop for j in range i+1 to n-1
- Run a loop for k in range j+1 to n-1
- If arr[k] is equal to arr[i]*arr[j], then update the value of ans=arr[k] and break out from the loop.
- Run a loop for k in range j+1 to n-1
- Run a loop for j in range i+1 to n-1
- Print ans.
Implementation
C++ program for find pair with the greatest product in array
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr.begin(),arr.end());
int ans=-1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(arr[k]==arr[i]*arr[j])
{
ans=arr[k];
break;
}
}
}
}
cout<<ans<<endl;
return 0;
}
6 10 2 2 4 30 35
4
JAVA program for find pair with the greatest product in array
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
Arrays.sort(arr);
int ans=-1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(arr[k]==arr[i]*arr[j])
{
ans=arr[k];
break;
}
}
}
}
System.out.println(ans);
}
}
9 35 7 5 8 2 2 56 3 1
56
Complexity Analysis for find pair with the greatest product in array
Time complexity
As we run 3 nested loops of size N, our total time complexity is O(N^3).
Space Complexity
We took only 1 extra variable, so we have a constant space complexity O(1).
Using hashing: Approach 2 for Find Pair with Greatest Product in Array
Main idea
we can store all the array elements in a hash table to check if an element is present or not in O(1) time. Now we can check for each element if a pair of its divisors whose product is equal to the element is present in the array or not.
Also, the range of the element is from 0 to 10^5, so we can simply use an array for the hash table.
And we have to check separately if the current element is a perfect square or is equal to 1.
Algorithm
- Create a hash table using an array and store all the array elements in it.
- Sort the array in decreasing order.
- Run a loop for I in range 0 to n-1
- Run a loop for j in range 2 to sqrt(arr[i])
- If j is divisible by arr[i] then, initialize another element k=arr[i]/j.
- If j and k are equal then, if the count of j is greater than 1 then arr[i] is the answer and break out from both loops.
- If the j and k are not equal then check if both the elements are present in the array of not, if yes then arr[i] is the answer and break from both loops.
- Run a loop for j in range 2 to sqrt(arr[i])
- If we have found an answer then print it else print -1.
For example if:
Input array = {10, 2, 2, 4, 30, 35}
Then the hash table will look like this:
The right column is shows the number and the right column shows their frequency in the array.
Implementation
C++ program for find pair with the greatest product in array
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> m(100001,0);
for (int i = 0; i < n; i++)
{
cin >> a[i];
m[a[i]]++;
}
sort(a.begin(), a.end(),greater<int>());
bool flag = false;
for (int i = 0; i<n; i++)
{
if (a[i] == 1)
{
if (m[a[i]] >= 3)
{
cout << a[i] << endl;
flag = true;
break;
}
else
{
continue;
}
}
for (int divisor_1 = 2; divisor_1 * divisor_1 <= a[i]; divisor_1++)
{
if (a[i] % divisor_1 == 0)
{
int divisor_2 = a[i] / divisor_1;
if (divisor_1 == divisor_2)
{
if (m[divisor_1] > 1)
{
cout << a[i] << endl;
flag = true;
break;
}
}
else
{
if ((m[divisor_1]>0) and (m[divisor_2]>0))
{
cout << a[i] << endl;
flag = true;
break;
}
}
}
}
if (flag)
{
break;
}
}
if (flag == false)
{
cout << "-1" << endl;
}
return 0;
}
11 22 72 9 8 11 33 123 21 45 10 5
72
Java program for find pair with the greatest product in array
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a=new int[n];
int[] m=new int[100001];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
m[a[i]]++;
}
Arrays.sort(a);
boolean flag = false;
for (int i = n-1; i>=0; i--)
{
if (a[i] == 1)
{
if (m[a[i]] >= 3)
{
System.out.println(a[i]);
flag = true;
break;
}
else
{
continue;
}
}
for (int divisor_1 = 2; divisor_1 * divisor_1 <= a[i]; divisor_1++)
{
if (a[i] % divisor_1 == 0)
{
int divisor_2 = a[i] / divisor_1;
if (divisor_1 == divisor_2)
{
if (m[divisor_1] > 1)
{
System.out.println(a[i]);
flag = true;
break;
}
}
else
{
if ((m[divisor_1]>0) && (m[divisor_2]>0))
{
System.out.println(a[i]);
flag = true;
break;
}
}
}
}
if (flag)
{
break;
}
}
if (flag == false)
{
System.out.println("-1");
}
}
}
11 22 72 9 8 11 33 123 21 45 10 5
72
Complexity Analysis
Time complexity
In the worst case, we iterate the whole array and for each element, we run a loop for sqrt(N). So the total time complexity is O(N^sqrt(N)).
Space complexity
We need to store a hash table so the space complexity is O(N).