Count Pairs Divisible By K

Time: O(n)

Space: O(k)

Problem Overview

Pair (i, j) counts only if (arr[i] + arr[j]) is divisible by k.

Intuition

Pair (i, j) counts only if (arr[i] + arr[j]) is divisible by k. Work modulo k: sums are divisible exactly when remainders r and (k − r) % k match. Scan once while tracking how many earlier elements had each remainder.

Algorithm

1Create freq[0 … k−1], initialized to 0.
2For each num: rem = num % k, need = (k − rem) % k.
3Add freq[need] to the answer (pairs with current element).
4Increment freq[rem].
5Return the total count.

Example Walkthrough

Input: arr = [1, 5, 7, 11], k = 6

1. num=1: rem=1, need=5, freq[5]=0 → count=0; freq[1]=1.
2. num=5: rem=5, need=1, freq[1]=1 → count=1 (pair 1+5); freq[5]=1.
3. num=7: rem=1, need=5, freq[5]=1 → count=2 (pair 5+7); freq[1]=2.
4. num=11: rem=5, need=1, freq[1]=2 → count=4 (pairs with both 1s); freq[5]=2.

Output: 4

Common Pitfalls

• need = (k − rem) % k handles rem = 0 (pairs both ≡ 0 mod k).
• Count freq[need] before incrementing freq[rem] so an element does not pair with itself.
• Use long for the answer if n is large — count can exceed 32-bit range.

Count Pairs Divisible By K.java

Java

// Approach: Remainder frequency — a pair sums to a multiple of k iff remainders r and (k-r)%k
// appear together. Scan left to right: add freq[(k - rem) % k] to count, then freq[rem]++.
// Time: O(n) Space: O(k)

class Solution {

    public int countKdivPairs(int[] arr, int k) {
        int[] freq = new int[k];
        int count = 0;

        for (int num : arr) {

            int rem = num % k;
            int need = (k - rem) % k;

            count += freq[need];
            freq[rem]++;
        }

        return count;
    }
}

Was this solution helpful?