C++ program to find pair with greatest product in array

In this tutorial, we are going to learn how to find a pair with the greatest product in an array in C++.

Naive Solution:

The simple solution is to consider all the possible pairs and to find the pair with the greatest product such that the product exists in the array.

Traverse the array and do the following steps for each element:

1. Iterate through the elements of the array and find if the picked element is divisible by them.
2. If the picked element is x and if it is divisible by y, check if there is an element x/y in the array. So if there is an element x/y in the array then compare x with the already existing greatest product. If x is greater than the already existing greatest product replace the greatest product with x.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j,k,maxi;
    cout<<"Enter the size of the array"<<endl;
    cin>>n;
    int a[n];
    cout<<"Enter the elements in the array"<<endl;
    for(i = 0;i < n;i++){
        cin>>a[i];
    }
    maxi = -1;
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            if(a[i]%a[j] == 0){
                for(k = 0;k < n;k++){
                    if(j != k && a[j]*a[k] == a[i]){
                        maxi = max(maxi,a[i]);
                    }
                }
            }
        }
    }
    if(maxi != -1){
        cout<<"The greatest product is: "<<maxi<<endl;
    }
    else{
        cout<<"No such product exists"<<endl;
    }
}

Output:

Enter the size of the array
6
Enter the elements in the array
2 10 5 6 20 8
The greatest product is: 20

Time Complexity: O(n³)

Optimal Solution:

1. Sort the given array.
2. Store the elements and their frequencies in a hash table. It is necessary to store the frequencies of the elements as all the keys in a hash table are discrete.
3. Traverse the array from the end and do the following steps for each element:
   a) Consider all the elements which are less than or equal to the square root of the picked element and check if the picked element is divisible by them.
   b) If x is the picked element and if it is divisible by y, check if there is an element x/y in the hash table. We can check for the presence of a number in the hash table in O(1). So if an element x/y exists in the hash table, we can say that x is the greatest product as the array is sorted.
   c) If there is a pair whose product is equal to the picked element halt the process or else continue the process.

Implementation:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j,k,maxi,flag;
    cout<<"Enter the size of the array"<<endl;
    cin>>n;
    int a[n];
    cout<<"Enter the elements in the array"<<endl;
    for(i = 0;i < n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    // Unordered map works like a hash table
    unordered_map<int,int> m;
    for(i = 0;i < n;i++){
        m[a[i]]++;
    }
    flag = 0;
    for(i = n-1;i >= 0;i--){
        j = 0;
        while(j < i && a[j] <= sqrt(a[i])){
            if(a[i]%a[j] == 0){
                if(a[i]/a[j] == a[j] && m[a[j]] >= 2){
                    maxi = a[i];
                    flag = 1;
                    break;
                }
                else if(a[i]/a[j] != a[j] && m[a[i]/a[j]] >= 1){
                    maxi = a[i];
                    flag = 1;
                    break;
                }
            }
            j++;
        }
        if(flag == 1){
            break;
        }
    }
    if(flag == 1){
        cout<<"The greatest product is: "<<maxi<<endl;
    }
    else{
        cout<<"No such product exists"<<endl;
    }

}

Output:

Enter the size of the array
6
Enter the elements in the array
4 3 9 3 10 5
The greatest product is: 9

Time Complexity: O(nlogn)

 

We hope that you have got a clear idea of how to write a C++ program to find a pair with the greatest product in an array.