Last Updated: 10 May, 2022
Count Pairs
Moderate
Asked in company
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).
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
Approaches
Approach:
- 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’.
- Check if their values are equal and their product is divisible by ‘D’, if true.
- Do another for loop to select the second element of the pair
- Return ‘RES’.
Approach:
- Using sieve of Eratosthenes we will precalculate the numer of multiples of some index ‘i’ having value ‘ARR[j]’ where ‘j’ is a multiple of ‘i’.
- Then we will simply take all indexes from ‘1’ to ‘N’ , say ‘i’ and add the corresponding number of multiples of ’k’ = ‘D/GCD(D, i)’ of value ‘ARR[i]’.
- Take care for the case when ‘i%k == 0’, by subtracting 1 from result, as here we are making the pair of indexes ‘(i, i)’.
- Up until this point we have counted a pair two times so we will return the (totalresult)/2.
Algorithm :
- Create an array of map(‘MP’) of size ‘N’ with ‘key, value’ type as ‘int, int’ respectively.
- We will precalculate the numer of multiples of some index ‘i’ having value ‘ARR[j]’ where ‘j’ is a multiple of ‘i’, by:
- Running a for loop from ‘i’ = 1 to ‘N’
- Do a for loop from ‘j’ = ‘i’ to ‘N’ and incrementing ‘j’ by ‘i’ in each iteration.
- Increment ‘MP[i][ARR[j]]’ by ‘1’.
- Do a for loop from ‘j’ = ‘i’ to ‘N’ and incrementing ‘j’ by ‘i’ in each iteration.
- Running a for loop from ‘i’ = 1 to ‘N’
- Create and initialize a ‘RES’ integer variable as ‘0’.
- Run a for loop from ‘i’ = 1 to ‘N’
- Create and Initialize a variable ‘K’ as smalles multiple required to satisfy ‘I * K % D = 0’
- Add ‘MP[K][ARR[i]]’ to ‘RES’
- If ‘K’ is a multiple of ‘I’ then,
- Decrease ‘K’ by ‘1’.
- Return ‘RES/2’.