Count Pairs Divisible by K

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

Example:

Input:

ARR = [4, 3, 5, 1, 4, 5], K = 5

Output:

3

Explanation:

The pairs whose sums are divisible by 5 are [4, 1], [5, 5], and [4, 1]. Thus, there are 3 pairs.

Constraints:

1

Question

Count Pairs Divisible by K

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

Example:

Input:

ARR = [4, 3, 5, 1, 4, 5], K = 5

Output:

Explanation:

The pairs whose sums are divisible by 5 are [4, 1], [5, 5], and [4, 1]. Thus, there are 3 pairs.

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

Count pairs in an array whose sum is divisible by a given integer K.

Iterate through the array and calculate the remainder of each element when divided by K.
Store the remainders in a hashmap along with their frequencies.
For each remainder R, check if K - R is present in the hashmap and add the product of their frequencies to the count.
Return the total count of pairs whose sum is divisible by K.