Count Pairs with Sum Divisible by K

Title: Count Pairs with Sum Divisible by K

Counting pairs whose sum is divisible by a number is a classic array and number theory interview question. In this guide, you will learn an O(n + k) approach that groups numbers by their remainder, walk through a full Java implementation, and practice the edge cases and follow up questions interviewers tend to ask.

Understanding the Problem

Given an integer array nums and a positive integer k, the task is to count index pairs (i, j) with i < j such that (nums[i] + nums[j]) % k == 0.

A direct approach checks every pair with a nested loop, which costs O(n²) time. This article builds a faster solution that groups numbers by the remainder they leave when divided by k, bringing the time down to O(n + k).

Approach

The key idea is that two numbers sum to a multiple of k only when their remainders modulo k add up to k, or both are 0. Group the array by remainder first, then combine the group sizes using simple combinatorics.

1. Read the array nums and the divisor k.
2. Create a frequency array remainderCount of size k, initialized to zero.
3. For every element in nums, compute its remainder with ((num % k) + k) % k so negative numbers map to a valid, non negative bucket, and increment that bucket in remainderCount.
4. Add remainderCount[0] choose 2 pairs to the running total, since any two elements that are already multiples of k sum to a multiple of k.
5. For every remainder r from 1 up to, but not including, k / 2, add remainderCount[r] * remainderCount[k - r] to the total, since one element from each complementary group sums to a multiple of k.
6. If k is even, separately add remainderCount[k / 2] choose 2 pairs, since two elements that both leave remainder k / 2 also sum to a multiple of k.
7. Return the accumulated total as the pair count.

Java Program

The following program implements the remainder grouping approach described above.

public class CountPairsDivisibleByK {

    public static long countPairs(int[] nums, int k) {
        int[] remainderCount = new int[k];
        for (int num : nums) {
            int remainder = ((num % k) + k) % k;
            remainderCount[remainder]++;
        }

        long pairs = pairCombinations(remainderCount[0]);

        for (int r = 1; r * 2 < k; r++) {
            pairs += (long) remainderCount[r] * remainderCount[k - r];
        }

        if (k % 2 == 0) {
            pairs += pairCombinations(remainderCount[k / 2]);
        }

        return pairs;
    }

    private static long pairCombinations(int count) {
        return (long) count * (count - 1) / 2;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int k = 3;
        long result = countPairs(nums, k);
        System.out.println("Pairs with sum divisible by " + k + ": " + result);
    }
}

Explanation of the Program

The method countPairs first builds remainderCount, an array where index r stores how many elements of nums leave remainder r when divided by k. Normalizing with ((num % k) + k) % k matters because Java’s % operator keeps the sign of the dividend, so a negative number can otherwise produce a negative, invalid array index.

The helper method pairCombinations returns count * (count - 1) / 2, the standard formula for choosing 2 items out of count without repetition. It is used once for the remainder 0 group and, when k is even, once more for the remainder k / 2 group, because in both cases a group pairs with itself.

The main loop runs only while r * 2 < k so that each pair of complementary remainders, such as 1 and k - 1, is combined exactly once. Running the loop all the way to k - 1 would multiply every product twice and double the final answer.

All intermediate sums are stored in a long accumulator. For large arrays, remainderCount[r] * remainderCount[k - r] can exceed the range of a 32 bit int, so the multiplication is done in long arithmetic.

Step-by-Step Trace

For nums = [3, 6, 9, 12, 7, 2] and k = 5, the target output is 4 pairs. After the first loop builds the frequency array, remainderCount holds [0, 1, 3, 1, 1] for remainders 0 through 4. The table below traces the second loop, where those counts are combined into the final answer.

At the end of each step, pairs holds the number of valid pairs found among all remainder groups processed so far.

Examples

Example 1: Counting Pairs with Positive Integers

With nums = {9, 7, 5, 3} and k = 6, the remainder groups are 3 with count 2, 1 with count 1, and 5 with count 1. Group 3 pairs with itself (9 + 3 = 12), and group 1 pairs with group 5 (7 + 5 = 12), for a total of 2 pairs.

int[] nums = {9, 7, 5, 3};
int k = 6;
System.out.println(countPairs(nums, k));
// Output: 2

Example 2: Handling Negative Numbers

With nums = {-7, -2, 5, 10} and k = 5, normalizing the remainders of -7 and -2 both produce 3, while 5 and 10 both produce 0. Only the remainder 0 group forms a valid pair (5 + 10 = 15), since remainder 3 has no complementary remainder 2 element to pair with.

int[] nums = {-7, -2, 5, 10};
int k = 5;
System.out.println(countPairs(nums, k));
// Output: 1

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this remainder grouping technique.

• Skipping remainder normalization. Using num % k directly leaves negative numbers with a negative remainder, such as -7 % 5 producing -2 in Java, which throws an ArrayIndexOutOfBoundsException when used to index remainderCount. Always normalize with ((num % k) + k) % k.
• Multiplying a group by itself. Writing remainderCount[0] * remainderCount[0] instead of the combination formula pairs every element with itself and inflates the count. Use count * (count - 1) / 2 for the remainder 0 and remainder k / 2 groups.
• Looping the full remainder range. Iterating r from 1 to k - 1 instead of stopping before k / 2 combines each complementary pair of remainders twice, doubling the final answer. Stop the loop as soon as r * 2 >= k.
• Accumulating pairs in an int. For large arrays, remainderCount[r] * remainderCount[k - r] can overflow a 32 bit int and wrap to a negative number. Declare the accumulator, and cast the product, as long.
• Allowing k to be zero. Calling countPairs with k = 0 creates a zero length remainderCount array, and the first num % k throws an ArithmeticException. Validate that k is at least 1 before processing the array.

Edge Cases to Test

Walk through these input shapes before calling the solution complete.

• Empty array or fewer than two elements
• k equal to 1
• Negative numbers mixed with positive numbers
• All elements identical
• k larger than the largest possible pair sum
• k even, exercising the remainder k / 2 group
• Large array where pair counts could overflow a 32 bit int

Additional Considerations

The remainder grouping approach runs in O(n + k) time: O(n) to build remainderCount and O(k) to combine the groups. Space usage is O(k) for the frequency array, a significant improvement over the O(n²) time and O(1) space of the brute force nested loop when k is small relative to n.

When k is very large, such as 10⁹, allocating an array of size k wastes memory even though only a few remainders ever appear. In that situation, replace remainderCount with a HashMap<Integer, Integer> keyed by the normalized remainder, trading a constant factor in lookup speed for space proportional to the number of distinct remainders actually seen.

Interview Follow-up Questions

An interviewer will often extend this problem once the base solution works.

• What if you need the actual pairs, not just the count? Store indices in a Map<Integer, List<Integer>> keyed by remainder instead of counts, then pair indices across complementary lists.
• What if k can be as large as one billion? Replace the remainderCount array with a HashMap<Integer, Integer> so memory scales with the number of distinct remainders observed, not with k itself.
• What if nums arrives as a stream of unknown length? Keep the same remainder frequency map, and before inserting each new number, add the current count for its complementary remainder to a running total, then increment the count for its own remainder.
• What if you must solve this with only a few extra variables beyond the input array? Sort the array first, then use a two pointer scan that matches the smallest and largest remainders, trading the O(k) frequency array for O(log n) sorting space.

Conclusion

Counting pairs whose sum is divisible by k is a clean demonstration of trading a nested loop for a single pass plus a small combinatorial pass over remainder groups. The same remainder grouping pattern shows up across many array problems, so it is worth internalizing the normalization step and the combination formula shown here.

Try adapting countPairs to return the matching index pairs, or to work against a HashMap when k is large, to deepen your understanding. You can learn more array based interview problems in the Arrays category on this site.