> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/count-pairs-in-array-whose-sum-is-divisible-by-k.md).

# Count pairs in array whose sum is divisible by K

Given an array **A\[]** and positive integer **K**, the task is to count total number of pairs in the array whose sum is divisible by **K**.\
Note : This question is generalised version of [this](https://www.geeksforgeeks.org/count-pairs-array-whose-sum-divisible-4/)

**Examples:**

```
Input : A[] = {2, 2, 1, 7, 5, 3}, K = 4
Output : 5
Explanation : 
There are five pairs possible whose sum
is divisible by '4' i.e., (2, 2), 
(1, 7), (7, 5), (1, 3) and (5, 3)

Input : A[] = {5, 9, 36, 74, 52, 31, 42}, K = 3
Output : 7
```

```java
class Solution {
    public int[] pairSumDivByK(int[] A, int K) {
        // Map of (Remainder after % K) -> Frequency
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int x : A) {
            int mod = x % K;
            int pairValue = K - mod;
            if (map.containsKey(pairValue))
                count += map.get(pairValue);
            map.put(mod, map.getOrDefault(mod, 0) + 1);
        }
        return count;
    }
}

```