Pair count.
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

Question

Pair count.

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.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1),

No Extra space is used in the array.

Time Complexity: O(n^2)Explanation:

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)

C++ (g++ 5.4)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where N is the number of elements in the array
*/

int pairCount(vector &arr, int k){

    // Initialise count with 0.
    int count = 0;

    // Iterate through all the pairs of array.
    for(int i = 0; i < arr.size(); i++){
        for(int j = i + 1; j < arr.size(); j++){

            // If the current pair sum is divisible by K, increase the count.
            if((arr[i] + arr[j]) % k == 0){
                count += 1;
            }
        }
    }

    // Finally return count.
    return count;
}

Python (3.5)

'''
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    Where N is the number of elements in the array
'''


from typing import List

def pairCount(arr: List[int], k: int) -> int:

    # Initialise count with 0.
    count = 0

    # Iterate through all the pairs of array.
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):

            # If the current pair sum is divisible by K, increase the count.
            if (arr[i] + arr[j]) % k == 0:
                count += 1

    # Finally return count.
    return count

Java (SE 1.8)


/*
	Time Complexity: O(N^2)
	Space Complexity: O(1)
	
	Where N is the number of elements in the array
*/

public class Solution {

	public static int pairCount(int[] arr, int k) {

		// Initialise count with 0.
		int count = 0;

		// Iterate through all the pairs of array.
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {

				// If the current pair sum is divisible by K, increase the count.
				if ((arr[i] + arr[j]) % k == 0) {
					count += 1;
				}
			}
		}

		// Finally return count.
		return count;

	}

}

Accepted Answer

Hashing Remainders

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

Space Complexity: O(1)Explanation:

O(K), Where K is the integer given.

We are maintaining a frequency array of K - 1 size. Hence the final space complexity is O(K).

Time Complexity: O(1)Explanation:

O(N + K), Where N is the number of elements in the array and K is the integer given.

We are iterating through the entire array once and once through the remainder frequency array. Hence the final time complexity is O(N + K)