Find the total number of good Triplets

Moderate
0/80
Average time to solve is 30m
4 upvotes
Asked in companies
LinkedInCultfit

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3 3
2 6 4
2 2 8
3 3
2 1 4 
2 2 2
Sample Output 1:
3
6
Explanation of sample input 1:
For the first test case, 
All possible good triplets of type 1 are (0,0,1), (2,0,2) and (2,1,2). There are no possible good triplets of type 2. Hence, the answer is 3 in this case.

For the second test case,
All possible good triplets of type 1 are (0,0,1), (0,0,2) and (0,1,2). All possible good triplets of type 2 are (0,1,2), (1,1,2) and (2,1,2). Hence, the answer is 6 in this case.
Sample Input 2:
2
3 4 
2 5 3
2 2 3 3
4 4
1 1 2 2    
1 1 1 4
Sample Output 2:
2
15
Hint

Generate all possible triplets and check for each triplet if the triplet follows the given conditions.

Approaches (2)
Brute Force

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 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.
  • Return the variable totalTriplets.
Time Complexity

O(N * (M ^ 2) + M * (N ^ 2)), where N denotes the number of elements in the array ARR1, M denotes the number of elements in the array ARR2.

 

We are traversing through the array ARR1, and in each iteration, it takes O(M^2) time to find the good triplets of type 1. Therefore it takes O(N * (M ^ 2)) time. Similarly, to find good triplets of type 2, it takes O(M * (N ^ 2)) time. Hence the overall time complexity is O(N * (M ^ 2) + M * (N ^ 2)).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Find the total number of good Triplets
Full screen
Console