Last Updated: 16 Apr, 2021
Find the total number of good Triplets
Moderate
Asked in companies
You are given two arrays, ‘ARR1’ and ‘ARR2’ of size ‘N’ and ‘M’. There are two types of good triplets.
Type 1: Triplet (i, j, k) If the square of ARR1[i] is equal to the product of ARR2[j] and ARR2[k], where 0 <= i <N and 0 <= j < k < M
Type 2: Triplet (i, j, k) If the square of ARR2[i] is equal to the product of ARR1[j] and ARR1[k], where 0 <= i <M and 0 <= j < k < N
Your task is to find the total number of good triplets.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the number of elements in the array 'ARR1', and the number of elements in the array 'ARR2' respectively.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR1'.
The third line of each test case contains 'M' space-separated integers denoting the elements of the array 'ARR2'.
Output Format:
For each test case, print a single line containing a single integer denoting the total number of good triplets following the given conditions.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= M <= 100
1 <= ARR1[i] <= 10^4
1 <= ARR2[i] <= 10^4
Where 'ARR1[i]' denotes the 'i'th' element of the array 'ARR1' and 'ARR2[i]' denotes the 'i'th' element of the array 'ARR2'.
Time limit: 1 sec.
Approaches
A simple method is to generate all possible triplets and check for each triplet if the triplet follows the given conditions.
Our approach will be to traverse through ARR1 and in each iteration, we will consider all pairs from ARR2 and check if the element from ARR1 and the pair from ARR2 follow the given conditions of type 1 triplet.
To obtain type 2 triplets, we will traverse through ARR2 and we will consider all pairs from ARR1 and check if the element from ARR2 and the pair from ARR1 follow the given conditions of type 2 triplet.
Algorithm:
- We will set totalTriplets as 0. The variable totalTriplets stores the total number of triplets following the given conditions.
- Iterate i from 0 to N-1
- Iterate j from 0 to M-1
- Iterate z from j+1 to M-1
- Check if the square of ARR1[i] is equal to the product of ARR2[j] and ARR2[z], then Increment totalTriplets by 1.
- Iterate z from j+1 to M-1
- Iterate j from 0 to M-1
- Iterate i from 0 to M-1
- Iterate j from 0 to N-1
- Iterate z from j+1 to N-1
- Check if the square of ARR2[i] is equal to the product of ARR1[j] and ARR1[z], then Increment totalTriplets by 1.
- Iterate z from j+1 to N-1
- Iterate j from 0 to N-1
- Return the variable totalTriplets.
Our approach will be to use a HashMap to store the frequency of the numbers. We will use HashMap to find the frequency of the quotient in the array when the square of the element of the other array is divided by the element in the array. We will find the good triplets of both types separately.
We will maintain a HashMap. To obtain triplets of type 1, we will iterate i from 0 to N-1, and we will iterate j from 0 to M-1, and at each iteration,
- We will check if the square of ARR1[i] can be divided by ARR2[j], and we will check if the HashMap contains the quotient, i.e., quotient when the square of ARR1[i] is divided by ARR2[j]. If the HashMap contains the quotient, then we will increment the answer by the frequency of the quotient present in the HashMap.
- We will insert ARR2[j] in the HashMap.
At the end of each pass of ARR1[i], we will delete all keys in the HashMap.
To obtain triplets of type 2, we will iterate i from 0 to M-1, and we will iterate j from 0 to N-1, and we will use a similar approach that is used to find the total number of good triplets of type 1.
Algorithm:
- We will set totalTriplets as 0. The variable totalTriplets stores the total number of triplets following the given conditions.
- Maintain a HashMap frequency
- Iterate i from 0 to N-1
- Iterate j from 0 to M-1
- Find square and quotient, which is equal to the square of ARR1[i] and quotient when square is divided by ARR2[j]
- Check if square is divisible by ARR2[j] and the key quotient is present in the frequency, then increment totalTriplets by frequency[quotient].
- Insert ARR2[j] in frequency
- Delete all keys present in the frequency. In frequency, we are trying to store the frequency of elements of ARR2 that are present till j index. We are deleting all keys present in frequency, so we can start the iteration of the next ARR1 element.
- Iterate j from 0 to M-1
- Iterate i from 0 to M-1
- Iterate j from 0 to N-1
- Find square and quotient, which is equal to the square of ARR2[i] and quotient when square is divided by ARR1[j]
- Check if square is divisible by ARR2[j] and the key quotient is present in the frequency, then increment totalTriplets by frequency[quotient].
- Insert ARR1[j] in frequency
- Delete all keys present in the frequency.
- Iterate j from 0 to N-1
- Return the variable totalTriplets.