Loading…

easyArraysSometimes asked

Divisible Sum Pairs

Q: How do you solve Divisible Sum Pairs using the Brute Force — Check Every Pair approach?

When to use it: Always open with this — it's the literal reading and a correct baseline for small n. Then say 'we can do better by thinking in remainders.' Translate the prompt directly: iterate all pairs `(i, j)` with `i < j` and count those where `(a[i] + a[j]) % k == 0`. **Why `j = i + 1`.** Starting the inner loop at `i + 1` ensures each unordered pair is examined exactly once and an element is never paired with itself — the same loop-invariant discipline as the brute-force Two Sum. **Why it's a fine baseline.** With `n ≤ 100` there are at most ~4950 pairs, so this passes instantly. It's worth writing first because it's obviously correct and gives you something to verify the optimal solution against. **Why we don't stop here.** The modulo check hides structure: whether a pair counts depends *only* on the two remainders mod k, not the values. Brute force ignores that and re-derives each remainder inside an n² loop. Recognizing the remainder structure lets us count complements in a single pass, which is the optimal approach. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Divisible Sum Pairs using the Remainder Buckets — One-Pass Complement Count (Optimal) approach?

When to use it: The answer they want. Frame it as 'Two Sum on remainders': bucket by value mod k and count complements as you go. Walk the array once, maintaining `count[r]` = how many already-seen elements have remainder `r` mod k. For each new element with remainder `r`, the elements it can pair with are precisely those already seen with the *complementary* remainder; add that bucket's count to the answer, then record the current element in its own bucket. **Deriving the complement.** Write each value as `value = q·k + r` where `r = value % k` lies in `[0, k)`. Then `a + b ≡ (r₁ + r₂) (mod k)`, so `(a + b) % k == 0` iff `r₁ + r₂` is `0` or `k`. Therefore the partner remainder for `r` is `k - r` — except when `r == 0`, where the partner is also `0`. Writing the complement as `(k - r) % k` folds both cases into one expression: for `r == 0`, `(k - 0) % k == 0`, exactly what we want, and it never indexes out of bounds at `k`. **Why look up before incrementing.** This is the same check-before-insert rule as Two Sum. By adding `count[(k - r) % k]` *before* doing `count[r]++`, the current element only pairs with elements that came *earlier* (`i < j`). If we incremented first, an element with `r == 0` (or any self-complementary remainder) would count itself, inflating the answer. **Why each later element scoops up all earlier partners at once.** When we reach index `j`, `count[(k - r) % k]` already holds *every* earlier index whose remainder completes `r`. Adding that whole bucket count in one step is what replaces the inner loop — we count all matching pairs `(i, j)` ending at `j` in `O(1)`. **Why O(k) space, not O(n).** We only ever store *how many* elements landed in each of the `k` remainder classes, never the elements themselves. There are exactly `k` classes, so the array is size `k` regardless of how large `n` is. Time complexity: O(n). Space complexity: O(k).

Arrays & Hashing · 27 of 83 · 7 min

Given an array of integers a and a positive integer k, count the number of (i, j) pairs where i < j and (a[i] + a[j]) is divisible by k.

In plain English

You count unordered pairs of distinct positions whose values sum to a multiple of k. The condition depends only on each value's remainder mod k: two values pair up iff their remainders are complementary (sum to k, or both zero).

Examples

Example 1

Input: a = [1, 2, 3, 4, 5, 6], k = 5
Output: 3
Note: Pairs summing to a multiple of 5: (1,4)=5, (2,3)=5, (4,6)=10. Indices (0,3), (1,2), (3,5).

Example 2

Input: a = [1, 3, 2, 6, 1, 2], k = 3
Output: 5
Note: Remainders mod 3: [1,0,2,0,1,2]. Complementary pairs: 1+2 and 0+0. Five qualifying pairs in total.

Example 3

Input: a = [2, 2, 2, 2], k = 4
Output: 6
Note: Every value has remainder 2, and 2 + 2 = 4 is divisible by 4, so all C(4,2) = 6 pairs qualify.

Constraints

2 ≤ n ≤ 100
1 ≤ k ≤ 100
1 ≤ a[i] ≤ 100
i < j (ordered pairs counted once)

Clarifying questions4First question: Does i < j mean each pair is counted once?Explore questions

Q1.Does i < j mean each pair is counted once?
Yes — (i, j) and (j, i) are the same pair and counted a single time. The one-pass complement count enforces this naturally by only looking backward.
Q2.Can the array have duplicates, and do duplicate pairs count separately?
Yes. If three elements share remainder r and 2r ≡ 0 mod k, all three pairwise combinations count. Bucket counts handle this automatically.
Q3.Are the values always positive?
In the original constraints, yes. If negatives were allowed you'd normalize with ((x % k) + k) % k to keep remainders in [0, k).
Q4.Could k be larger than every element?
Yes — then remainders are just the values themselves, and pairs only count when two values sum exactly to k. The same logic still applies.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count pairs (i, j) with i < j where (a[i] + a[j]) % k == 0. Brute force checks all pairs in O(n²). The optimal trick: a sum is divisible by k exactly when the two remainders mod k add up to k (or both are 0). Tally how many elements fall in each remainder bucket, then for each new element with remainder r, add the count of elements already seen with the complementary remainder (k - r) % k. One pass, O(n) time, O(k) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can translate 'sum divisible by k' into a statement about complementary remainders, and then apply the Two-Sum complement-count pattern on those remainders instead of brute-forcing all pairs.

Where candidates slip

Using k - r instead of (k - r) % k (out-of-bounds / missed self-complement when r == 0), or counting the current element's bucket before looking up the complement so an element pairs with itself.

How to stand out

Say 'this is Two Sum on remainders'. Derive the complement formula (k - r) % k out loud, explain the r == 0 special case, and note the same pattern handles Subarray Sums Divisible by K.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Check Every Pair	`O(n²)`	`O(1)`	Always open with this — it's the literal reading and a correct baseline for small n. Then say 'we can do better by thinking in remainders.'	Read
2	Remainder Buckets — One-Pass Complement Count (Optimal)Optimal	`O(n)`	`O(k)`	The answer they want. Frame it as 'Two Sum on remainders': bucket by value mod k and count complements as you go.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision preview(a[i] + a[j]) % k == 0?r1 + r2 == 0 or == k ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Check Every Pair

TimeO(n²)SpaceO(1)

Always open with this — it's the literal reading and a correct baseline for small n. Then say 'we can do better by thinking in remainders.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The problem literally asks about pairs (i, j) with i < j. What's the most direct way to enumerate them?

2Hint 2Explore hint

Two nested loops: outer i from 0 to n-1, inner j from i+1 to n-1, so every unordered pair is visited once.

3Hint 3Explore hint

For each pair test (a[i] + a[j]) % k == 0 and increment a counter when it holds.

A · Core idea

Translate the prompt directly: iterate all pairs (i, j) with i < j and count those where (a[i] + a[j]) % k == 0.

Why `j = i + 1`. Starting the inner loop at i + 1 ensures each unordered pair is examined exactly once and an element is never paired with itself — the same loop-invariant discipline as the brute-force Two Sum.

Why it's a fine baseline. With n ≤ 100 there are at most ~4950 pairs, so this passes instantly. It's worth writing first because it's obviously correct and gives you something to verify the optimal solution against.

Why we don't stop here. The modulo check hides structure: whether a pair counts depends only on the two remainders mod k, not the values. Brute force ignores that and re-derives each remainder inside an n² loop. Recognizing the remainder structure lets us count complements in a single pass, which is the optimal approach.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 2, 3, 4, 5, 6], k = 5

Array state

i=3, j=5

4 + 6 = 10 → divisible by 5

[0]

[1]

[2]

i ↓

[3]

[4]

j ↓

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int divisibleSumPairs(int n, int k, List<Integer> ar) { int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((ar.get(i) + ar.get(j)) % k == 0) {Explore the full code

solution.javaJava

Brute Force — Check Every Pair — reference

2 teaching notes

1
public int divisibleSumPairs(int n, int k, List<Integer> ar) {
2
    int count = 0;
3
    for (int i = 0; i < n; i++) {
4
        // j starts at i+1 so each unordered pair is counted once and never self-pairs.
5
        for (int j = i + 1; j < n; j++) {
6
            // The literal divisibility test on the pair's sum.
7
            if ((ar.get(i) + ar.get(j)) % k == 0) {
8
                count++;
9
            }
10
        }
11
    }
12
    return count;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Brute force is the right first move and a correct oracle for testing, but the modulo in the condition is a hint: the answer depends on residues, not raw values. That observation is the doorway to the linear solution.

ComplexityO(n²) time, O(1) space — There are n(n-1)/2 ≈ n²/2 ordered pairs with i < j; we test each once with O(1) arithmetic. That's O(n²) time and just one counter of space.

E · Edge cases and pitfalls3Starting j at 0 — pairs an element with itself and double-counts.Explore edge cases

Pitfalls

Starting j at 0 — pairs an element with itself and double-counts.
Using == k instead of % k == 0 — misses sums like 10 that are multiples beyond k.
Assuming this is too slow for the given constraints — it's actually fine for n ≤ 100, but you should still present the optimal.

03.2

Approach 2 of 2 · Optimal

Remainder Buckets — One-Pass Complement Count (Optimal)

TimeO(n)SpaceO(k)

The answer they want. Frame it as 'Two Sum on remainders': bucket by value mod k and count complements as you go.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When is a + b divisible by k? Write a = qk + r1 and b = pk + r2. The sum is divisible by k exactly when r1 + r2 is 0 or k.

2Hint 2Explore hint

So for an element with remainder r, its valid partners are the already-seen elements whose remainder is (k - r) % k. How many of those have you seen?

3Hint 3Explore hint

Keep a count[] array of size k. For each element compute r, add count[(k - r) % k] to the answer, THEN increment count[r]. Lookup before increment, just like Two Sum.

A · Core idea

Walk the array once, maintaining count[r] = how many already-seen elements have remainder r mod k. For each new element with remainder r, the elements it can pair with are precisely those already seen with the complementary remainder; add that bucket's count to the answer, then record the current element in its own bucket.

Deriving the complement. Write each value as value = q·k + r where r = value % k lies in [0, k). Then a + b ≡ (r₁ + r₂) (mod k), so (a + b) % k == 0 iff r₁ + r₂ is 0 or k. Therefore the partner remainder for r is k - r — except when r == 0, where the partner is also 0. Writing the complement as (k - r) % k folds both cases into one expression: for r == 0, (k - 0) % k == 0, exactly what we want, and it never indexes out of bounds at k.

Why look up before incrementing. This is the same check-before-insert rule as Two Sum. By adding count[(k - r) % k] before doing count[r]++, the current element only pairs with elements that came earlier (i < j). If we incremented first, an element with r == 0 (or any self-complementary remainder) would count itself, inflating the answer.

Why each later element scoops up all earlier partners at once. When we reach index j, count[(k - r) % k] already holds every earlier index whose remainder completes r. Adding that whole bucket count in one step is what replaces the inner loop — we count all matching pairs (i, j) ending at j in O(1).

Why O(k) space, not O(n). We only ever store how many elements landed in each of the k remainder classes, never the elements themselves. There are exactly k classes, so the array is size k regardless of how large n is.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 2, 6, 1, 2], k = 3

Hash-map state

x=1, r=1

lookup 2

ValueIndex / state

0→ 0

1→ 1

2→ 0

Continue scanning

complement 2 → count[2]=0, add 0; then count[1]=1

Final result5

C · Code with teaching comments

solution.javaJava

Remainder Buckets — One-Pass Complement Count (Optimal) — optimal

5 teaching notes

1
public int divisibleSumPairs(int n, int k, List<Integer> ar) {
2
    // One bucket per remainder class — k of them, so O(k) space.
3
    int[] count = new int[k];
4
    int pairs = 0;
5
    for (int x : ar) {
6
        // The element's remainder; the only thing that matters for pairing.
7
        int r = x % k;
8
        // Partner remainder. The outer % k makes r==0 map to 0 instead of out-of-range
9
        // k.
10
        int complement = (k - r) % k;
11
        // Every earlier element in the complement bucket forms a valid pair — added
12
        // before the increment so we only look backward.
13
        pairs += count[complement];
14
        // Record this element for future elements to find.
15
        count[r]++;
16
    }
17
    return pairs;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(k) spaceOpen the invariant and proofExplore the proof

Divisibility of a sum is a fact about remainders, and remainders inhabit a universe of only k values. That shrinks the 'partner' question from 'which of the n values?' to 'which of the k buckets?', and a bucket count answers it in O(1). It's literally Two Sum with value replaced by value % k and target replaced by k. The same residue-bucketing powers Subarray Sums Divisible by K (bucket prefix sums mod k) and Continuous Subarray Sum.

ComplexityO(n) time, O(k) space — One pass over n elements, each doing O(1) work: a modulo, an array read, an array write. Total O(n) time. The bucket array has k entries → O(k) space, independent of n.

E · Edge cases and pitfalls6a = [2, 2, 2, 2], k = 4 — Every remainder is 2; complement (4-2)%4 = 2. Buckets accumulate so the four 2's form 0+1+2+3 = 6 pairs. Self-complementary remainder handled by lookup-before-increment.Explore edge cases

Edge cases handled

a = [2, 2, 2, 2], k = 4Every remainder is 2; complement (4-2)%4 = 2. Buckets accumulate so the four 2's form 0+1+2+3 = 6 pairs. Self-complementary remainder handled by lookup-before-increment.
a = [3, 6, 9], k = 3All remainders 0; complement (3-0)%3 = 0. Three zero-remainder elements → 0+1+2 = 3 pairs. Confirms (k-r)%k maps r=0 to bucket 0, not out of bounds.
a = [1, 1], k = 5Both remainders 1; complement 4, never seen → 0 pairs. Shows non-complementary remainders contribute nothing.

Pitfalls

Using k - r instead of (k - r) % k — out-of-bounds index k when r == 0, and misses zero-remainder pairs.
Incrementing count[r] before the lookup — lets self-complementary elements pair with themselves.
Allocating count of size n instead of k — wastes space and confuses the bucket index with the element index.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int divisibleSumPairs(int n, int k, List<Integer> ar) { int[] count = new int[k]; int pairs = 0; for (int x : ar) { int r = x % k;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong complement formula for remainder 0

When r == 0 the partner remainder is also 0, but k - r = k is out of bounds for a size-k array. (k - r) % k folds k back to 0.

Explore the code comparison

Don't write this

int complement = k - r;          // == k when r == 0
pairs += count[complement];      // index out of bounds

Write this instead

int complement = (k - r) % k;    // 0 when r == 0
pairs += count[complement];

Increment before lookup (self-pairing)

If you bump count[r] first, an element whose remainder is its own complement (like 0, or k/2 when k is even) gets counted against itself.

Explore the code comparison

Don't write this

count[r] += 1
pairs += count[(k - r) % k]

Write this instead

pairs += count[(k - r) % k]
count[r] += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Remainder buckets + complement count (mod-k Two Sum)

Code pattern to memorize

count = [0]*k
pairs = 0
for x in a:
    r = x % k
    pairs += count[(k - r) % k]
    count[r] += 1

Rules to remember

1(a + b) % k == 0 ⇔ (a % k) + (b % k) is 0 or k. The complement of remainder r is (k - r) % k.
2The (k - r) % k (not just k - r) is essential: when r == 0, the complement must be 0, and k - 0 = k would index out of bounds.
3Count the complement before incrementing the current bucket — same check-before-insert discipline as Two Sum, so an element never pairs with itself.
4This is Two Sum on remainders: replace 'value seen' with 'remainder bucket count'.
5k is the number of buckets, so space is O(k), not O(n) — usually tiny.

Use this pattern when

Count (not just find) pairs whose sum satisfies a divisibility or modular condition
Any 'how many pairs sum to a multiple of k' / 'sum is congruent to t mod k' prompt
Streaming counts where you tally complements as you scan
The pairing condition can be expressed purely in terms of residues mod k

Choose another pattern when

You need the actual indices of one specific pair, not a count → store buckets of indices, or just brute force for small n
Condition isn't modular (e.g. product divisible, or exact target sum) → different decomposition
k can be huge relative to n → still fine (O(k) space), but a hash map keyed by remainder avoids allocating a giant array

Interview takeaway

Divisibility of a sum is a statement about remainders, and remainders live in a tiny universe of size k. Bucketing by remainder turns an O(n²) pair scan into a one-pass complement count — the exact same complement-lookup idea as Two Sum, just modular. You'll reuse it in Subarray Sums Divisible by K and Continuous Subarray Sum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo Sum on Remainders. Recognise it whenever a pair/subarray condition is modular: reduce each value to value % k, and the partner is the complementary residue (k - r) % k. Bucket counts replace the inner loop. Same shape as Subarray Sums Divisible by K and Continuous Subarray Sum.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Subarray Sums Divisible by K
Coming soon
Same remainder-bucket idea, but bucket prefix sums mod k and count equal residues.
Continuous Subarray Sum
Coming soon
Track first index of each prefix-sum remainder mod k to detect a divisible subarray.
Two Sum
The non-modular ancestor — complement lookup on values instead of remainders.

Same pattern

←

Zigzag Conversion

Continue · Next problem

Frequency Queries

easyArraysSometimes asked

Divisible Sum Pairs

Arrays & Hashing · 27 of 83 · 7 min

Given an array of integers a and a positive integer k, count the number of (i, j) pairs where i < j and (a[i] + a[j]) is divisible by k.

In plain English

Examples

Example 1

Input: a = [1, 2, 3, 4, 5, 6], k = 5
Output: 3
Note: Pairs summing to a multiple of 5: (1,4)=5, (2,3)=5, (4,6)=10. Indices (0,3), (1,2), (3,5).

Example 2

Input: a = [1, 3, 2, 6, 1, 2], k = 3
Output: 5
Note: Remainders mod 3: [1,0,2,0,1,2]. Complementary pairs: 1+2 and 0+0. Five qualifying pairs in total.

Example 3

Input: a = [2, 2, 2, 2], k = 4
Output: 6
Note: Every value has remainder 2, and 2 + 2 = 4 is divisible by 4, so all C(4,2) = 6 pairs qualify.

Constraints

2 ≤ n ≤ 100
1 ≤ k ≤ 100
1 ≤ a[i] ≤ 100
i < j (ordered pairs counted once)

Clarifying questions4First question: Does i < j mean each pair is counted once?Explore questions

Q1.Does i < j mean each pair is counted once?
Yes — (i, j) and (j, i) are the same pair and counted a single time. The one-pass complement count enforces this naturally by only looking backward.
Q2.Can the array have duplicates, and do duplicate pairs count separately?
Yes. If three elements share remainder r and 2r ≡ 0 mod k, all three pairwise combinations count. Bucket counts handle this automatically.
Q3.Are the values always positive?
In the original constraints, yes. If negatives were allowed you'd normalize with ((x % k) + k) % k to keep remainders in [0, k).
Q4.Could k be larger than every element?
Yes — then remainders are just the values themselves, and pairs only count when two values sum exactly to k. The same logic still applies.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Using k - r instead of (k - r) % k (out-of-bounds / missed self-complement when r == 0), or counting the current element's bucket before looking up the complement so an element pairs with itself.

How to stand out

Say 'this is Two Sum on remainders'. Derive the complement formula (k - r) % k out loud, explain the r == 0 special case, and note the same pattern handles Subarray Sums Divisible by K.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Check Every Pair	`O(n²)`	`O(1)`	Always open with this — it's the literal reading and a correct baseline for small n. Then say 'we can do better by thinking in remainders.'	Read
2	Remainder Buckets — One-Pass Complement Count (Optimal)Optimal	`O(n)`	`O(k)`	The answer they want. Frame it as 'Two Sum on remainders': bucket by value mod k and count complements as you go.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Check Every Pair

TimeO(n²)SpaceO(1)

Always open with this — it's the literal reading and a correct baseline for small n. Then say 'we can do better by thinking in remainders.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The problem literally asks about pairs (i, j) with i < j. What's the most direct way to enumerate them?

2Hint 2Explore hint

Two nested loops: outer i from 0 to n-1, inner j from i+1 to n-1, so every unordered pair is visited once.

3Hint 3Explore hint

For each pair test (a[i] + a[j]) % k == 0 and increment a counter when it holds.

A · Core idea

Translate the prompt directly: iterate all pairs (i, j) with i < j and count those where (a[i] + a[j]) % k == 0.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 2, 3, 4, 5, 6], k = 5

Array state

i=3, j=5

4 + 6 = 10 → divisible by 5

[0]

[1]

[2]

i ↓

[3]

[4]

j ↓

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Brute Force — Check Every Pair — reference

2 teaching notes

1
public int divisibleSumPairs(int n, int k, List<Integer> ar) {
2
    int count = 0;
3
    for (int i = 0; i < n; i++) {
4
        // j starts at i+1 so each unordered pair is counted once and never self-pairs.
5
        for (int j = i + 1; j < n; j++) {
6
            // The literal divisibility test on the pair's sum.
7
            if ((ar.get(i) + ar.get(j)) % k == 0) {
8
                count++;
9
            }
10
        }
11
    }
12
    return count;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — There are n(n-1)/2 ≈ n²/2 ordered pairs with i < j; we test each once with O(1) arithmetic. That's O(n²) time and just one counter of space.

E · Edge cases and pitfalls3Starting j at 0 — pairs an element with itself and double-counts.Explore edge cases

Pitfalls

Starting j at 0 — pairs an element with itself and double-counts.
Using == k instead of % k == 0 — misses sums like 10 that are multiples beyond k.
Assuming this is too slow for the given constraints — it's actually fine for n ≤ 100, but you should still present the optimal.

03.2

Approach 2 of 2 · Optimal

Remainder Buckets — One-Pass Complement Count (Optimal)

TimeO(n)SpaceO(k)

The answer they want. Frame it as 'Two Sum on remainders': bucket by value mod k and count complements as you go.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When is a + b divisible by k? Write a = qk + r1 and b = pk + r2. The sum is divisible by k exactly when r1 + r2 is 0 or k.

2Hint 2Explore hint

So for an element with remainder r, its valid partners are the already-seen elements whose remainder is (k - r) % k. How many of those have you seen?

3Hint 3Explore hint

Keep a count[] array of size k. For each element compute r, add count[(k - r) % k] to the answer, THEN increment count[r]. Lookup before increment, just like Two Sum.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 2, 6, 1, 2], k = 3

Hash-map state

x=1, r=1

lookup 2

ValueIndex / state

0→ 0

1→ 1

2→ 0

Continue scanning

complement 2 → count[2]=0, add 0; then count[1]=1

Final result5

C · Code with teaching comments

solution.javaJava

Remainder Buckets — One-Pass Complement Count (Optimal) — optimal

5 teaching notes

1
public int divisibleSumPairs(int n, int k, List<Integer> ar) {
2
    // One bucket per remainder class — k of them, so O(k) space.
3
    int[] count = new int[k];
4
    int pairs = 0;
5
    for (int x : ar) {
6
        // The element's remainder; the only thing that matters for pairing.
7
        int r = x % k;
8
        // Partner remainder. The outer % k makes r==0 map to 0 instead of out-of-range
9
        // k.
10
        int complement = (k - r) % k;
11
        // Every earlier element in the complement bucket forms a valid pair — added
12
        // before the increment so we only look backward.
13
        pairs += count[complement];
14
        // Record this element for future elements to find.
15
        count[r]++;
16
    }
17
    return pairs;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(k) spaceOpen the invariant and proofExplore the proof

Edge cases handled

a = [2, 2, 2, 2], k = 4Every remainder is 2; complement (4-2)%4 = 2. Buckets accumulate so the four 2's form 0+1+2+3 = 6 pairs. Self-complementary remainder handled by lookup-before-increment.
a = [3, 6, 9], k = 3All remainders 0; complement (3-0)%3 = 0. Three zero-remainder elements → 0+1+2 = 3 pairs. Confirms (k-r)%k maps r=0 to bucket 0, not out of bounds.
a = [1, 1], k = 5Both remainders 1; complement 4, never seen → 0 pairs. Shows non-complementary remainders contribute nothing.

Pitfalls

Using k - r instead of (k - r) % k — out-of-bounds index k when r == 0, and misses zero-remainder pairs.
Incrementing count[r] before the lookup — lets self-complementary elements pair with themselves.
Allocating count of size n instead of k — wastes space and confuses the bucket index with the element index.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int divisibleSumPairs(int n, int k, List<Integer> ar) { int[] count = new int[k]; int pairs = 0; for (int x : ar) { int r = x % k;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong complement formula for remainder 0

When r == 0 the partner remainder is also 0, but k - r = k is out of bounds for a size-k array. (k - r) % k folds k back to 0.

Explore the code comparison

Don't write this

int complement = k - r;          // == k when r == 0
pairs += count[complement];      // index out of bounds

Write this instead

int complement = (k - r) % k;    // 0 when r == 0
pairs += count[complement];

Increment before lookup (self-pairing)

If you bump count[r] first, an element whose remainder is its own complement (like 0, or k/2 when k is even) gets counted against itself.

Explore the code comparison

Don't write this

count[r] += 1
pairs += count[(k - r) % k]

Write this instead

pairs += count[(k - r) % k]
count[r] += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Remainder buckets + complement count (mod-k Two Sum)

Code pattern to memorize

count = [0]*k
pairs = 0
for x in a:
    r = x % k
    pairs += count[(k - r) % k]
    count[r] += 1

Rules to remember

1(a + b) % k == 0 ⇔ (a % k) + (b % k) is 0 or k. The complement of remainder r is (k - r) % k.
2The (k - r) % k (not just k - r) is essential: when r == 0, the complement must be 0, and k - 0 = k would index out of bounds.
3Count the complement before incrementing the current bucket — same check-before-insert discipline as Two Sum, so an element never pairs with itself.
4This is Two Sum on remainders: replace 'value seen' with 'remainder bucket count'.
5k is the number of buckets, so space is O(k), not O(n) — usually tiny.

Use this pattern when

Count (not just find) pairs whose sum satisfies a divisibility or modular condition
Any 'how many pairs sum to a multiple of k' / 'sum is congruent to t mod k' prompt
Streaming counts where you tally complements as you scan
The pairing condition can be expressed purely in terms of residues mod k

Choose another pattern when

You need the actual indices of one specific pair, not a count → store buckets of indices, or just brute force for small n
Condition isn't modular (e.g. product divisible, or exact target sum) → different decomposition
k can be huge relative to n → still fine (O(k) space), but a hash map keyed by remainder avoids allocating a giant array

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Subarray Sums Divisible by K
Coming soon
Same remainder-bucket idea, but bucket prefix sums mod k and count equal residues.
Continuous Subarray Sum
Coming soon
Track first index of each prefix-sum remainder mod k to detect a divisible subarray.
Two Sum
The non-modular ancestor — complement lookup on values instead of remainders.

Same pattern

←

Zigzag Conversion

Continue · Next problem

Frequency Queries