Pair count.

Moderate

0/80

Contributed by

4 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
6 5
4 3 5 1 4 5
4 3
1 3 0 2

Sample Output 1:

3
2

Explanation:

For the first test case, 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.

For the second test case, ‘ARR’ = [1, 3, 0, 2], and ‘K’ = 3.  In the given array the pair sums divisible by ‘K’ are [1, 2], [3, 0]. Since there are a total of 2 pairs, the answer is 2.

Sample Input 2:

2
7 3
1 2 3 4 5 6 7
2 5
4 2

Sample Output 2:

7
0

Hint 1

Hint 2

Try iterating over all possible pairs.

Approaches (2)

Approach 1

Approach 2

Brute Force

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

Time Complexity

O(N^2), Where N is the number of elements in the array.

For each index in the array, we are iterating over the entire array. Hence the final time complexity is O(N^2)

Space Complexity

O(1),

No Extra space is used in the array.

(100% EXP penalty)

Pair count.

Console