Given an integer array of length N (N>=2), we need to find the maximum product obtained by multiplying any two unique elements of the array.
Approach 1
The naive approach for this problem is to use two for loops to access all the possible pairs of unique elements in the array and check for the maximum product.
Time Complexity : O(n2)
LET US SEE THE CODE:
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main()
{
/*
N : stores the length of array
i : used to iterate through the array
j : used to iterate through the array
product : used to store the maximum product
*/
int N,i,j,product;
cout << "Enter length of array" << endl;
cin >> N; // Taking array length as input
vector<int> arr(N); // Stores array elements
cout << "Enter array elements" << endl;
for(i=0;i<N;i++) // Loop to take array elements as input
{
cin >> arr[i];
}
product=INT_MIN; // initialising product to minimum possible integer
for(i=0;i<N;i++) // loop to get the first element of a pair
{
for(j=i+1;j<N;j++) // loop to get the second element of a pair
{
product=max(product,(arr[i]*arr[j])); // finding the maximum product of all possible pairs
}
}
cout << "Maximum product is " << product;
return 0;
}
TEST CASE:
Enter length of array 5 Enter array elements -9 -7 5 2 9 Maximum product is 63
Approach 2
The idea here is to find the two elements having largest magnitude and two elements having smallest magnitude using sorting. Generally, there are two cases possible in an array :
- When array do not contain negative integers :- In this case, we can simply return the product of first two largest elements because product of larger elements give larger product.
- When array contains negative integers :- In this case, there may arise a condition where the least two negative numbers have more magnitude than the largest two positive numbers.
Eg- consider the array of length 4 having elements {7,6,-8,-9}.
Here, ((-8)*(-9)) > (7*6) as |-8| and |-9| are greater than |7| and |6| and have same sign.
So maximum product is (-8)*(-9)=72.
So, we can say that finding the maximum of product of first two elements and product of last two elements after sorting is efficient than finding the maximum of products obtained by all unique pairs of elements.
Time Complexity : O(nlogn)
LET US SEE THE CODE:
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main()
{
/*
N : stores the length of array
i : Used to iterate through the array
product : stores the maximum product
*/
int N,i,product;
cout << "Enter length of array" << endl;
cin >> N; // Taking length of array as input
vector<int> arr(N); // Stores array elements
cout << "Enter array elements" << endl;
for(i=0;i<N;i++) // Loop to take array elements as input
{
cin >> arr[i];
}
sort(arr.begin(),arr.end()); // sorting the array
product=max((arr[0]*arr[1]),(arr[N-1]*arr[N-2])); // finding the maximum of product of two largest elements and two smallest elements
cout << "Maximum product is " << product;
return 0;
}
TEST CASE:
Enter length of array 4 Enter array elements 7 4 -9 -6 Maximum product is 54
Approach 3
This approach uses same idea used in APPROACH 2 but does not use sorting to find the largest and smallest elements.
We simply iterate through the array to find the largest and smallest elements.
Time Complexity : O(n)
LET US SEE THE CODE:
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main()
{
/*
N : contains the length of array
i : used to iterate through the array
max1 : used to store the first maximum element in array
max2 : used to store the second maximum element in array
min1 : used to store the first minimum element in array
min2 : used to store the second minimum element in array
max1_index : used to store the index of first maximum element in array
min1_index : used to store the index of first minimum element in array
*/
int N,i,product,max1,max2,min1,min2,max1_index=0,min1_index=0;
cout << "Enter length of array" << endl;
cin >> N; //Taking length of array as input
vector<int> arr(N); // Stores array elements
cout << "Enter array elements" << endl;
for(i=0;i<N;i++) // loop to take array elements as input
{
cin >> arr[i];
}
min1=INT_MAX; // initialising min1 to maximum possible integer
max1=INT_MIN; // initialising max1 to minimum possible integer
for(i=0;i<N;i++) // loop to find the first largest and smallest element in array
{
if(arr[i]>=max1) // condition to check if arr[i] is greater than or equal to max1
{
max1=arr[i]; // If yes, replacing the value of max1 to arr[i]
max1_index=i; // If yes, replacing max1_index with index of arr[i]
}
if(arr[i]<=min1) // condition to check if arr[i] is less than or equal to min1
{
min1=arr[i]; // If yes, replacing the value of min1 to arr[i]
min1_index=i; // If yes, replacing min1_index with index of arr[i]
}
}
min2=INT_MAX; // initialising min2 to maximum possible integer
max2=INT_MIN; // initialising max2 to minimum possible integer
for(i=0;i<N;i++) // loop to find the second largest and smallest element in array
{
// condition to check if arr[i] is greater than or equal to max2 and arr[i] is not the max1
if(arr[i]>=max2 && i!=max1_index)
{
max2=arr[i]; // If yes, replacing the value of max2 to arr[i]
}
// condition to check if arr[i] is less than or equal to min2 and arr[i] is not the min1
if(arr[i]<=min2 && i!=min1_index)
{
min2=arr[i]; // If yes, replacing the value of min2 to arr[i]
}
}
product=max((max1*max2),(min1*min2));
cout << "Maximum product is " << product;
return 0;
}
TEST CASE:
Enter length of array 5 Enter array elements 0 5 6 -3 -2 Maximum product is 30