Given an array of n integer, find the maximum element in an array that is also equal to product of two other element in the array.
Please don’t propose O(n2) solutions since 1<=n<=106
You can have an O(n * sqrt(n) + n * log(n)) solution.
Basically, sort the array O (n * log(n)) and for each number x in decreasing order, for each of it’s factor i, check whether i and x / i exists in the array. If yes, you get the answer.
If you have some limit on each value, say 1<=x<=10^6, you can go with something like this:
start from i = 2 to MAX_VALUE(only those which exist in array), now for each multiple num of i, check if num ans num/i exists in the array. If yes, num is a candidate answer. Complexity will be O(n/2 + n/3 + n/4 + …) == O(n*log(n))
UPD: Adding Code for 2nd approach.:
//assuming int array freq[] which is stores frequency of each element.
int freq[1000001];
//input
int ans = 0;
for(int i = 2; i<= 1000000; i++){
if(freq[i]){
for(int j = 2 * i; j <= 1000000; j+=i){
int num = j / i;
if(num == i){
// consider case {5,5,25} -> 25 can be the answer
if(freq[i] > 1 && freq[j] > 0){
ans = max(ans , j);
}
}else{
if(freq[i] > 0 && freq[j] > 0 && freq[num] > 0){
ans = max(ans , j);
}
}
}
}
}
Brute force for one number of the pair to be 1 or 0 if required.
For which one?
#include<stdio.h>
void main()
{
int a[100],b[100],c[100][100],n,i,j,greatest;
printf(“enter the number of elements\n”);
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(“enter the %dth element\n”,i);
scanf("%d",&a[i]);
}
printf("\n");
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
b[j]=(a[i])*(a[j]);
c[i][j]=b[j];
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",c[i][j]);
}
printf("\n");
}
}
after this…compare the numbers in the C matrix with that of the original matrix , and store the ones which match in a separate array and find the greatest among them. the greatest among them is your answer.
Sort the array with O(n*logn). Then rest can be observed by factorizing with O(n * sqrt(n)) and using maps. Start from the right hand side i.e. largest element.
For N = 10^6, a solution of complexity \mathcal{O}(N\sqrt{N}) generally not the expected solution. For this problem we can sort the elements in \mathcal{O}(N\log{N}) and use a hash map to store the elements and use 2 pointer approach to get the solution in linear time. So the overall complexity is \mathcal{O}(N\log{N} + N) .Sort the elements and set the left pointer to 1 and right pointer to N-1 .Then if product of A[lptr]\times A[rptr] is greater than MaxValue then decrease right pointer otherwise check whether the product is an element of the array using the hashmap and increase the left pointer. Repeat until lptr < rptr . (also keep a check whether the three elements are distinct)
If the product of elements is less than max value but is not present in an array then whether the left pointer will be incremented or the right pointer will be decremented?
Can you please explain, how the complexity of this approach is Nlog(N)
and please also look at the last ans in this thread, that seems to be the better approach. I couldn’t understand it, if you could, then help me out with that also.