Last Updated: 6 Oct, 2020
Max Product Count
Moderate
Asked in companies
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.
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
Approaches
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:
- We create a Map that stores the product as key and frequency as value.
- 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.
- 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.