Last Updated: 17 Nov, 2021

Pair count.

Moderate

Asked in companies

Solve now

Problem statement

You are given an array ‘ARR’, and a positive integer ‘K’. Your task is to count the total number of pairs whose sum is divisible by ‘K’.

For example:

You are given, ‘ARR’ =[4, 3, 5, 1, 4, 5], and ‘K’ = 5.  In the given array the pair sums divisible by ‘K’ are [4,1], [5, 5], [4, 1]. Since there are a total of 3 pairs, the answer is 3.

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’ representing the size of the array and the integer ‘K’.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.

Output Format:

For each test case, print a single integer representing the number of pairs divisible by ‘K’.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
2 <= N < 10^6
1 <= K <= 10^9
0 <= arr[i] <= 10^9

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Solve now

Approaches

01 Approach

In this approach, try to iterate through all possible pairs in the array and count the number of pairs that are divisible by ‘K’.

Algorithm:

Set count as 0
Iterate i through all the indices of the arr
- Iterate j from i + 1 to the size of arr
  - If arr[i] + arr[j] is divisible by k, increase count by 1.
Return count

Solve now

02 Approach

In this approach, we will store the modulus of each element in the array when it is divided by ‘K’. We create a frequency count where at position ‘i’ in the frequency count, it stores the number of elements which give remainder ‘i’ when divided by ‘K’.

Therefore two numbers ‘a’ and ‘b’ sum is divisible by ‘K’ if a%K+ b%K is equal to K.

So, we just multiply the count of numbers whose remainder sum to K.

Algorithm:

Initialise an empty array remFreq of size K
Iterate num through the arr
- Increase remFreq[num % k] by 1.
Set pairNums as remFreq[0]*(remFreq[0] - 1) / 2
Iterate i from 1 to k + 1 // 2 - 1
- Add remFreq[i]*remFreq[k - i] to pairNums
Return pairNums

Solve now