Max Product Count

Moderate
0/80
Average time to solve is 35m
65 upvotes
Asked in companies
AmazonHSBCAmerican Express

Problem statement

You are given an array 'ARR' of 'N' distinct integers.

Your task is to find the product 'P' with the highest count('C') of quadruples which follow p * q = r * s where p, q, r, and s are elements of the array with different indexes.

Note: 
1. Quadruple p*q = r*s is the same as r*s = p*q.

2. If 2 or more products have the same count of quadruples, print the lowest value of the product i.e if (P1, P2) are the 2 products with the same count of such quadruples(C1 = C2) then 'P' = min(P1, P2).

3. If no such quadruple exists('C' = 0), return 0.

Example:

If the given array is [3, 4, 6, 2, 1], then the answer would be 6 1. Because there are two products 'P' i.e 6 and 12 which have the highest and same count 'C' of quadruples, i.e 'C' = 1. Therefore the lowest value of the product 'P' is the answer i.e 6.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains integer 'N' denoting the size of the array.

The second line of each test case contains 'N' single space-separated integers representing the array elements of array 'ARR'.
Output Format: 
For each test case, print two single space-separated integers 'P', and 'C', denoting the value of the product and the count of quadruples respectively.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
4 <= N <= 10^2  
1 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the element at index 'i' in the array 'ARR'.

Time Limit: 1 sec
Sample Input 1:
2
6
2 6 3 4 1 12 
6
4 1 7 2 6 5
Sample Output 1:
12 3
0
Explanation for Sample 1:
In test case 1, there are a total of 3 quadruples for product 12 in the given array as given below:

2 6 and 3 4, (p = 2, q = 6, r = 3 and s = 4).
2 6 and 1 12, (p = 2, q = 6, r = 1 and s = 12).
3 4 and 1 12, (p = 3, q = 4, r = 1 and s = 12).

Thus, product('P') = 12, Count('C') = 3. No other value has 3 or more Quadruples.

In test case 2, every pair of elements forms a different value on multiplying, and thus no Quadruple is formed by the given set of elements of the array. Hence 0 Quadruples formed.
Sample Input 2:
1
8
7 2 10 1 8 3 9 4
5
4 2 1 8 2
Sample Output 2:
8 1
8 3
Explanation for Sample Output 2:
In test case 1, there is only one quadruple in the given array i.e (p = 2, q = 4, r = 8 and s = 1). Thus, Product('P') = 8 and Count('C') = 1. No other Quadruple is possible.

In test case 2, there are a total of 3 quadruples for product 8 in the given array as given below:

1 8 and 2i 4, (p = 1, q = 8, r = 2i and s = 4).
1 8 and 2ii 4, (p = 1, q = 8, r = 2ii and s = 4).
2i 4 and 2ii 4, (p = 2i, q = 4, r = 2ii and s = 4).

Here, 2i and 2ii denote the two different occurrences of 2 in the array.

Thus, Product('P') = 8, Count('C') = 3. No other value has 3 or more Quadruples.
Hint

Think of storing one pair product and its frequency in a data structure.

Approaches (1)
Hash Map

In this problem, If we observe closely then we have to only take care of one pair of products. Let’s take an example, where ‘ARR’ = [1,2,3,4,6,8,12,24]. There are a total of 4 distinct pairs with product 24 in the given array i.e (1,24), (2,12), (3,8), (4,6). The total number of quadruples that can be formed with these 4 pairs is 6 as given below:

 

        (1, 24) = (2,12)

        (1, 24) = (3, 8)

        (1, 24) = (4, 6)

        (2,12) = (3, 8)

        (2,12) = (4, 6)

        (3, 8) = (4, 6)

 

So, we can find the highest number of quadruples by finding the product pair with max frequency and then calculate the frequency.

 

The steps are as follows:

 

  1. We create a Map that stores the product as key and frequency as value.
  2. We will find all the pairs by using two nested loops in which the outer loop will pick the first element and the inner loop pick the second element of the pair and store their product and frequency in the map.
  3. Iterate through the map and find the product with maximum frequency and store in ‘maxProd’ and frequency in ‘FREQ’ and there will be ('FREQ')C2 combinations that will be the total quadruples.
Time Complexity

O(N ^ 2),  where ‘N’ is the size of the array.

 

Since we are iterating for each element in the array in (O(N)) time, and the inner loop for each element will be iterated in O(N) time, i.e. a nested loop. Thus the overall time complexity will be O(N ^ 2). 

Space Complexity

O(N ^ 2), where ‘N’ is the size of the array.

 

Since we are storing products of all pairs of the array in the map, and the total number of pairs in the array of N Integers can be NC2 = (N * (N - 1)) / 2. Thus total space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
Max Product Count
Full screen
Console