Coding Interview Patterns Module 6 – Prefix sums and difference arrays

Divisibility with prefix remainders

Count the stretches of an array whose total is a multiple of k by grouping running totals by remainder, with negative remainders fixed in every language.

Intermediate
20 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0, quickjs 0.32.0 and Java temurin-25.0.4+101.0.LTS
By MySmartCoPilot

Free: The problem: stretches that fill whole crates. With a pass: the other 9 sections and 3 interview answers, about 15 minutes.

What you will learn

Count subarrays whose sum is divisible by k from the remainders of running totals
Normalise negative remainders in Java, C++, Go and JavaScript
Detect a divisible subarray of at least two elements
Choose between a list of k counters and a hash map from the limits on k

Before you start

Count subarrays with a target sum

What you’ll learn · Before you start

What you will learn

Count subarrays whose sum is divisible by k from the remainders of running totals
Normalise negative remainders in Java, C++, Go and JavaScript
Detect a divisible subarray of at least two elements
Choose between a list of k counters and a hash map from the limits on k

Before you start

Count subarrays with a target sum

On this page

Testing every stretch of a 200,000-entry order log for a total that is a multiple of k takes about 2 × 10¹⁰ tests. A stretch’s total is divisible by k when it leaves no remainder, so the question is about remainders, not about the totals themselves. Counting such stretches is a close relative of counting stretches with a fixed total: running total: The sum of the items seen so far, updated with one addition per item, so the totals of every prefix of a list cost one pass instead of a new sum each. More in “Getting unstuck: heuristics and using hints” turn each stretch into a difference of two numbers, and divisibility only cares about what those numbers leave over after division by k. Counting those remainders takes a list of k counters when k is small, or a hash map when it is large.

Below are an original problem about crates and cancelled orders, the cost of trying every stretch at its limits, and the signal that turns it into a single pass.

The problem: stretches that fill whole crates

The problem

A wholesaler ships units in crates of k. Its order log lists, in order, how many units each entry adds to the shipment: an order is positive, a cancellation that takes units back is negative. A stretch of consecutive entries can be packed or unpacked in whole crates exactly when its net total is a multiple of k: 0, k, −k, 2k and so on. Count those stretches. Limits: 1 ≤ n ≤ 2 × 10⁵, −10⁵ ≤ units[i] ≤ 10⁵ and 1 ≤ k ≤ 10⁵.

units = [3, -8, 3, 5, 8, -9] and k = 5 give 4: entries 0 to 1 and entries 1 to 2 both net −5, one crate taken back; entries 1 to 3 net 0; entry 3 alone is 5.
[4, 2, 6] and k = 3 give 3: [4, 2], [6] and the whole log.
[1, 2, 4] and k = 7 give 1: only the whole log, which nets 7.

The brute force: every stretch, tested

For each first entry, extend the stretch one entry at a time, keep its net total, and test whether k divides it. The test is O(1), but there are n(n + 1)/2 stretches. Step through the 21 tests of the first example:

Interactive · step by step Every stretch of the first log, tested Step through the first entries. Each step extends the stretch to the end of the log and tests every net total it passes.

The drawing shows the whole scene; its 8 steps are listed below.

Every step as text

The log. The log is [3, −8, 3, 5, 8, −9] and a crate holds 5 units. For each first entry, the brute force extends the stretch one entry at a time and tests whether 5 divides its net total.
First entry 0. From entry 0 the net totals are 3, −5, −2, 3, 11 and 2. Only −5 is a multiple of 5: entries 0 to 1 take one crate back.
First entry 1. From entry 1 the totals are −8, −5, 0, 8 and −1. Two are multiples of 5: entries 1 to 2 net −5, and entries 1 to 3 net 0.
First entry 2. From entry 2 the totals are 3, 8, 16 and 7. None of them is a multiple of 5.
First entry 3. From entry 3 the totals are 5, 13 and 4. Entry 3 alone fills one crate.
First entry 4. From entry 4 the totals are 8 and −1, and neither is a multiple of 5.
First entry 5. The last row has one stretch, entry 5 alone, with a net total of −9.
21 tests for 4 stretches. 6 entries made 6 + 5 + 4 + 3 + 2 + 1 = 21 tests, n(n + 1)/2, to find 4 stretches. At 200,000 entries the same loops make 20,000,100,000 tests.

The same loops on longer logs, with the time they take:

Every stretch tested, and the time it would take at the limit Python · brute/crates_brute.py

"""Counts the stretches of an order log whose net units fill whole crates, by checking every stretch, and times it."""
import random
import time


def full_crate_stretches_brute(units, k):
    """For each first entry, extend the stretch one entry at a time and test its total."""
    count = 0
    for first in range(len(units)):
        net = 0
        for last in range(first, len(units)):
            net += units[last]
            count += net % k == 0
    return count


print(full_crate_stretches_brute([3, -8, 3, 5, 8, -9], 5))
print(full_crate_stretches_brute([4, 2, 6], 3))
print(full_crate_stretches_brute([1, 2, 4], 7))

rng = random.Random(3)
timings = []
for n in (1_000, 2_000):
    units = [rng.randint(-100_000, 100_000) for _ in range(n)]
    started = time.perf_counter()
    full_crate_stretches_brute(units, 12)
    timings.append((time.perf_counter() - started) / (n * (n + 1) // 2))
    print(f"{n:,} entries: {n * (n + 1) // 2:,} totals tested")

n = 200_000
minutes = timings[-1] * n * (n + 1) / 2 / 60
print(f"{n:,} entries: {n * (n + 1) // 2:,} totals, roughly {minutes:,.0f} minutes at the speed of the last run")

Output

4
3
1
1,000 entries: 500,500 totals tested
2,000 entries: 2,001,000 totals tested
200,000 entries: 20,000,100,000 totals, roughly 53 minutes at the speed of the last run

This output changes from run to run: the time depends on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 crates_brute.py

At 2 × 10⁵ entries that is 2 × 10¹⁰ tests. The last line turns the measured speed into the time for the full log, far beyond any time limit, and compiled code at a rough 10⁸ simple steps a second would still need more than three minutes.

Checkpoint

Check: Which stretches fill whole crates · The brute force and its cost

Question 1 of 2 Crates hold 5 units. Which net totals of a stretch can be packed or unpacked in whole crates?
Choose every answer that is right.

−5 3 0 10 −7
Show the answer: Question 1 of 2
Answer:
- −5
- 0
- 10
A stretch counts exactly when its net total is a multiple of k: 0, k, −k, 2k and so on, negative totals included.
Question 2 of 2 How many totals does the brute force test on a log of 1,000 entries?
Type a number.
Your answer totals

Show the answer: Question 2 of 2

Answer: 500500 totals

One test per stretch: n(n + 1)/2 = 1,000 × 1,001 / 2 = 500,500, the number the program printed.

What to notice

Whether a number is a multiple of k depends only on its remainder after division by k, and every stretch total is the difference of two running totals. Together, those two facts turn a question about all n(n + 1)/2 stretches into a question about the n + 1 running totals and their remainders. Watch the negative entries: a running total can drop below zero, and not every language agrees on the remainder of a negative number.

Checkpoint

Check: What points to remainders

One question Whether the net total of a stretch is a multiple of k depends on what?
Choose one answer.

On whether the total is positive Only on the remainder that total leaves after division by k On the largest entry of the stretch On the length of the stretch

Show the answer: One question

Answer: Only on the remainder that total leaves after division by k

That fact, and that every stretch total is the difference of two running totals, turn the question into one about the n + 1 running totals and their remainders.

The questions below cover the problem, its brute force and the signal; a wrong answer brings an easier one on the same idea, a right one a harder one.

Equal remainders, counted in one pass Pro: opens with a Pro, Premium or Ultimate pass

In this part:

Why equal remainders mean a multiple of k
The sign of a remainder in 14 languages, recorded
The count in 14 languages
Three slips, caught by a stress test
A divisible stretch of at least two entries
Four variants, each a small change to the count
Practise: stretches that leave r units over
- Count the stretches that leave r units over
Interview questions
- A JavaScript solution counts the subarrays whose sum is divisible by k by counting equal values of total % k over the running totals. It matches the brute force on every test with non-negative values and fails once negative values appear. Find the bug without running the code, and give a fix that also works in Java, C++ and Go.
- Your count of subarrays with sums divisible by k keeps an array of k counters, one per remainder. The limits change to k up to 10⁹ with n up to 2 × 10⁵ and values up to 10⁹ in absolute value. What breaks, what do you change, and what does each choice cost in time and memory?
- Decide whether some run of at least two consecutive values has a sum that is a multiple of k, for up to 10⁵ values. Why is the remainder-counting map not enough as it is, what do you store instead, and why must that map never be overwritten?
Key takeaways

2 diagrams · 5 runnable examples (Java, Python) · 1 exercise with sample tests · 3 interview answers · about 38 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

References

The Python Language Reference: binary arithmetic operations (the % operator) (Python Software Foundation)
The Java Language Specification, Java SE 25: 15.17.3 Remainder Operator % (Oracle)
Java SE 25 API: Math.floorMod (Oracle)
The Java Language Specification, Java SE 25: 4.2.2 Integer Operations (Oracle)
Arithmetic operators (multiplicative operators, built-in remainder) (cppreference.com)
The Go Programming Language Specification: arithmetic operators (integer division and remainder) (The Go Authors)
ECMAScript language specification: Number::remainder (Ecma International (TC39))
Arithmetic operators (C language): division and remainder (cppreference.com)
Arithmetic operators (C# reference): remainder operator % (Microsoft)
PHP manual: arithmetic operators (The PHP Group)
Primitive type i32 (Rust standard library): rem_euclid (The Rust Project)
The Swift Programming Language: Basic Operators (remainder operator) (Swift.org)
class Integer (Ruby documentation): % and remainder (ruby-lang.org)
Kotlin standard library: mod (JetBrains)
Dart API: num operator % (Euclidean modulo) (Dart (Google))
The Swift Programming Language: The Basics (Int) (Swift.org)

Report a problem with this lesson

In this module: Prefix sums and difference arrays

Prefix sums for instant range totals Free lesson, Pro answers: 25 minutes
Count subarrays with a target sum Free core, Pro depth: 7 of 20 minutes free
Divisibility with prefix remainders Free intro, Pro: 5 of 20 minutes free
Balanced stretches: ±1 and XOR prefixes Free intro, Pro: 5 of 20 minutes free

Your country

Divisibility with prefix remainders

What you will learn

Before you start

What you will learn

Before you start

The problem: stretches that fill whole crates

The brute force: every stretch, tested

What to notice

Equal remainders, counted in one pass Pro: opens with a Pro, Premium or Ultimate pass

References

Related tools