Count Pairs

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
Walmart

Problem statement

Given an array ‘ARR’ of ‘N’ integers and a number ‘D’. Find the number of pair of indexes (‘i’ and ‘j’) in the array such that ‘ARR[i] = ARR[j]’ for ‘i != j’ and ‘(i * j) % D = 0’. ‘I’ and ‘j’ are 1 index-based.

EXAMPLE: 
Input: 
'N' = 5, ‘D’ = 6
‘ARR’ = [2, 2, 2, 2, 2]

Output: 2

The pair of indexes satisfying the given conditions are (2, 3) and (3, 4).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases. For each test case

The first line of each test case contains two integers ‘N’ and ‘D’.
The second line of each test case contains ‘N’ integers denoting the elements of array ‘ARR’.
Output format : 
  For each test case, print the number of pairs of indexes satisfying the given conditions.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
2 <= 'N', ‘D’  <= 10^5
1 <= ‘ARR[i]’ <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
7 2
3 3 3 2 3 2 2
4 2
2 1 1 2
Sample Output 1 :
6
2
Explanation Of Sample Input 1 :
In the first test case,
The pair of indexes satisfying the given conditions are (4, 7),(6, 7), (4, 6), (1, 2), (2, 3), and (2, 5).
Hence the answer is ‘6’.

In the second test case,
The pair of indexes satisfying the given conditions are (1, 4), and (2, 3).
Hence the answer is ‘2’.
Sample Input 2 :
2
4 3
4 3 7 6
4 4
3 7 5 1
Sample Output 2 :

0 0

Hint

Try Brute Force.

Approaches (2)
Brute Force

Approach: 
 

  1. Select each possible pair and check whether they satisfy the condition or not.
     

Algorithm :  
 

  • Create and initialize variable ‘RES’ with ‘0’ to store the result.
  • Do a for loop for the first element of the pair
    • Do another for loop to select the second element of the pair
      • Check if their values are equal and their product is divisible by ‘D’, if true.
        • Increase ‘RES’.
  • Return ‘RES’.
Time Complexity

O(N * N), Where ‘N’ is the length of the array ‘ARR’.

We are selecting the first element of the pair in ~N and for each first element we are trying all the elements in the array which takes another ~N time., the time complexity will be O(N * N).

Space Complexity

O(1).


The ‘RES’ will only take ~1 space, Hence the space complexity will be O(1).

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