Approach-2: Use Hashing to find pair with greatest product in array
Idea
We can use a hash table to check whether an array element is present or not in O(1) time. Now we can determine whether or not an element has a pair of divisors whose product is equal to the element.
And we must separately determine whether the current element is a perfect square or equal to 1.
Algorithm
- Sort the given array.
- In a hash table, store the elements and their frequencies. Because the keys in a hash table are all discrete, the frequencies of the elements must be stored.
-
Traverse the array from beginning to end, performing the following steps for each element:
a) Examine all the elements that are less than or equal to the square root of the chosen element to see if it is divisible by them.
b) If x is the selected element and it is divisible by y, check the hash table for an element x/y. In O(1), we can test for the presence of a number in the hash table. As the array is sorted, if an element x/y exists in the hash table, we can say that x is the greatest product.
Pictorial Representation
Now, let us discuss the Implementation in different languages:
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i,j,k,maxi;
bool flag;
cout<<"Enter the size of the array"<<endl;
cin>>n;
int arr[n];
cout<<"Enter the elements in the array"<<endl;
for(i = 0;i < n;i++){
cin>>arr[i];
}
sort(arr,arr+n);
/*
Unordered map works like a hash table
*/
unordered_map<int,int> m;
for(i = 0;i < n;i++){
m[arr[i]]++;
}
flag = false;
for(i = n-1;i >= 0;i--){
j = 0;
while(j < i && arr[j] <= sqrt(arr[i])){
if(arr[i]%arr[j] == 0){
if(arr[i]/arr[j] == arr[j] && m[arr[j]] >= 2){
maxi = arr[i];
flag = true;
break;
}
else if(arr[i]/arr[j] != arr[j] && m[arr[i]/arr[j]] >= 1){
maxi = arr[i];
flag = true;
break;
}
}
j++;
}
if(flag){
break;
}
}
if(flag){
cout<<"The greatest product is: "<<maxi<<endl;
}
else{
cout<<"No such product exists"<<endl;
}
}
You can also try this code with Online C++ Compiler
Output
Time Complexity: O(nlogn), where n is the length of the array.
Space Complexity: O(n), where n is the length of array.
Implementation in Java
/*
Java program to find the largest pair with largest product
*/
import java.util.*;
class CodingNinjas {
/*
Function to find greatest number
*/
static int findGreatestOne(int arr[], int n) {
/*
Store occurrences of all
elements in hash array
*/
Map < Integer, Integer > map = new HashMap < > ();
for (int i = 0; i < n; i++) {
if (map.containsKey(arr[i])) {
map.put(arr[i], map.get(arr[i]) + 1);
} else {
map.put(arr[i], map.get(arr[i]));
}
}
/*
m[arr[i]]++;
Sort the array and traverse
all elements from end.
*/
Arrays.sort(arr);
for (int i = n - 1; i >= 0; i--) {
/*
For every element, check if there is another
element which divides it.
*/
for (int j = 0; j < i && arr[j] <= Math.sqrt(arr[i]); j++) {
if (arr[i] % arr[j] == 0) {
int result = arr[i] / arr[j];
/*
Check if the result value exists in array
or not if yes the return arr[i]
*/
if (result != arr[j] && map.get(result) == null || map.get(result) > 0) {
return arr[i];
}
/*
To handle the case like arr[i] = 4
and arr[j] = 2
*/
else if (result == arr[j] && map.get(result) > 1) {
return arr[i];
}
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of array");
int n = sc.nextInt();
System.out.println("Enter the elements of array");
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(findGreatestOne(arr, n));
}
}
You can also try this code with Online Java Compiler
Output:
Time Complexity: O(nlogn), where n is the length of the array.
Space Complexity: O(n), where n is the length of array.
Read More - Time Complexity of Sorting Algorithms
Frequently Asked Questions
What is hashmap in java?
The Java collections framework's HashMap class implements the functionality of the hash table data structure. It organises elements into key/value pairs. In this context, keys are unique identifiers that are used to associate each value on a map. The Map interface is implemented by the HashMap class.
What is a 2-d matrix?
An array of arrays is one way to define the two-dimensional array. The 2D array is structured as matrices, which are made up of a number of rows and columns.
Where do we use a hashset?
For high-performance operations involving a set of unique data, a hashset is typically utilised. HashSet's internal structure is enhanced for quicker searches because it only contains unique components.
What is the HashMap searching time complexity?
For lookup, HashMap takes O(1) complexity.
What is the HashMap insertion time complexity?
For insertion, HashMap takes O(1) complexity.
Conclusion
In this article, we've discussed the problem to find pair with greatest product in array. We had also seen the example, time and space complexity, and output of the program on user input, along with an efficient approach to solving using hashing.
If you want to learn more about such problems, visit the given links below:
Recommended problems -
Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, Java Programming, System Design, etc. Have a look at the interview experiences and interview bundle for placement preparations. And also, enroll in our courses and refer to the mock test and problems available.
Do upvote our blog to help other ninjas grow.
Happy Learning!!
117+ registered 