Check If Array Pairs Are Divisible by k: Remainder Counting

You are given an integer array arr of even length n and an integer k. You need to determine whether it is possible to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k.

This is LeetCode 1497: Check If Array Pairs Are Divisible by k, a medium problem that tests your understanding of modular arithmetic and frequency counting. The brute force approach tries all possible pairings, which is far too slow. The key insight is that divisibility by k depends only on remainders.

Why this problem matters

Pairing problems are common in interviews, and they often hide a simpler structure behind what looks like a combinatorial explosion. Trying all possible pairings of an array with 10 elements already gives you hundreds of thousands of combinations. For arrays with up to 100,000 elements, brute force is impossible.

This problem teaches you to reduce a pairing question to a counting question. Instead of asking "which specific elements should pair together," you ask "do the right numbers of elements exist in each category?" That shift from individual matching to aggregate counting is a pattern that shows up in problems involving divisibility, complementary sums, and frequency-based validation.

The key insight

If two numbers a and b have a sum divisible by k, then (a % k + b % k) % k == 0. This means their remainders must add up to exactly k (or both be zero). So remainder r pairs with remainder k - r.

Three rules govern valid pairing:

1. Elements with remainder 0 must pair among themselves, so count[0] must be even.
2. If k is even, elements with remainder k/2 must pair among themselves, so count[k/2] must be even.
3. For every other remainder r from 1 to k-1, the count of remainder r must equal the count of remainder k - r.

If all three conditions hold, valid pairing is possible. You never need to figure out which specific elements pair together.

The solution

def canArrange(arr, k):
    count = [0] * k
    for num in arr:
        count[num % k] += 1

    if count[0] % 2 != 0:
        return False

    for r in range(1, k // 2 + 1):
        if r == k - r:
            if count[r] % 2 != 0:
                return False
        else:
            if count[r] != count[k - r]:
                return False

    return True

The solution counts how many elements fall into each remainder bucket, then verifies the pairing constraints. You iterate through the array once to build the counts, then iterate through at most k/2 buckets to verify. No sorting, no nested loops, no backtracking.

Visual walkthrough

The walkthrough shows the entire process: compute remainders, count frequencies, then verify that complementary buckets have matching counts. Each check is O(1), and you only need to check k/2 pairs of buckets. The algorithm runs in a single pass through the array followed by a quick validation loop.

Complexity analysis

Time: You iterate through the array once to count remainders (O(n)), then check at most k/2 bucket pairs (O(k)). Since k is typically much smaller than n, the total is O(n).

Space: The frequency array has exactly k slots, regardless of the input size. This is O(k) extra space.

The building blocks

1. Remainder frequency counting

count = [0] * k
for num in arr:
    count[num % k] += 1

This is the same pattern used in problems like counting characters in a string or grouping elements by a property. You reduce each element to a category (here, its remainder) and count how many fall into each one. The remainder array acts as a hash map with integer keys from 0 to k-1.

2. Complement pairing validation

for r in range(1, k // 2 + 1):
    if r == k - r:
        if count[r] % 2 != 0:
            return False
    else:
        if count[r] != count[k - r]:
            return False

This pattern checks whether complementary groups can be fully matched. You have seen it before in Two Sum (where you look for target - num in a hash map) and in problems like Pairs of Songs With Total Durations Divisible by 60. The principle is the same: for every element in group A, there must be a corresponding element in group B.

Edge cases

• All elements divisible by k (arr = [5, 10, 15, 20], k = 5): every element has remainder 0, so count[0] must be even. Here it is 4, which works.
• k = 1: every integer is divisible by 1, so any pair sums to a multiple of 1. As long as the array length is even, the answer is always True.
• Negative numbers (arr = [-1, 1, -2, 2, -3, 3], k = 3): in Python, (-1) % 3 == 2, so -1 goes into bucket 2. It pairs naturally with elements in bucket 1. No special handling needed.
• Odd-length array: the problem guarantees even length, but if it did not, the answer would always be False since you cannot form complete pairs.
• Large k with sparse remainders: most buckets will have count 0. Zero equals zero, so empty complementary buckets pass validation trivially.
• k = 2: only two buckets (0 and 1). Bucket 0 must have even count, and bucket 1 must also have even count (since 1 pairs with 1 when k=2, because k-1=1=r).

From understanding to recall

The remainder counting approach makes sense once you see it. Group by remainder, check that complements match. But under interview pressure, it is easy to forget the edge case for remainder 0, miss the special handling when r == k - r, or get confused about negative number remainders in your language of choice.

Spaced repetition turns this understanding into automatic recall. You practice writing the remainder counting loop and the validation check from scratch at increasing intervals. After a few rounds, you see "pairs divisible by k" and immediately think: count remainders, check complements, handle the zero bucket. No hesitation, no fumbling with edge cases.

The remainder-complement pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Two Sum - The foundational complement-finding pattern using a hash map
• Subarray Sum Equals K - Prefix sums with frequency counting for divisibility-related problems
• Pairs of Songs With Total Durations Divisible by 60 - Nearly identical structure with k=60, pairing song durations by remainder

CodeBricks breaks the check if array pairs are divisible by k problem into its remainder counting and complement validation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a modular pairing question shows up in your interview, you do not think about it. You just write it.