Prefix Sums Example: Till Runs That Pay Out in Whole £5 Notes

Sales and refunds on a till roll: a run totals a multiple of 5 exactly when two prefix totals leave the same remainder.

A run's total is a multiple of k exactly when the prefix totals at its two ends leave the same remainder after division by k, so a map keyed by remainder counts those runs in one pass. A till roll records sales and refunds in pounds, 4 −6 3 2 −3, and the manager asks how many stretches of consecutive lines total a whole number of £5 notes, counting a total of 0 as a whole number. Nothing in the question says sum or range, but each stretch's total is p[j + 1] − p[i], and that difference is a multiple of 5 when both totals leave the same remainder.

The remainder must be the same for every total, and that is where the languages differ. Python's % takes the sign of the divisor, so -2 % 5 is 3. Java's and TypeScript's % take the sign of the dividend, so the same expression gives −2, and −2 never matches the 3 it should. The fix in every language is ((s % k) + k) % k, which is never negative.

The till roll's prefix totals and their remainders after division by 5, from runs in each language
Position	Prefix total	Remainder in Python	Remainder in Java and TypeScript
0	0	0	0
1	4	4	4
2	−2	3	−2
3	1	1	1
4	3	3	3
5	0	0	0

Python's remainders hold two matching pairs: 0 at positions 0 and 5, the whole roll totalling £0, and 3 at positions 2 and 4, the stretch 3 2 totalling £5. Java and TypeScript, with the plain %, see only the first pair. The Python listing counts with the plain % and with the fix.

till_runs.pypy

def remainder(total: int, k: int) -> int:
    return ((total % k) + k) % k


def count_runs_divisible(amounts: list[int], k: int, to_remainder) -> int:
    seen: dict[int, int] = {0: 1}
    total = runs = 0
    for amount in amounts:
        total += amount
        key = to_remainder(total, k)
        runs += seen.get(key, 0)
        seen[key] = seen.get(key, 0) + 1
    return runs


till = [4, -6, 3, 2, -3]
totals = [0]
for amount in till:
    totals.append(totals[-1] + amount)
print("prefix totals", *totals)
print("plain % remainders", *[total % 5 for total in totals])
print("plain %:", count_runs_divisible(till, 5, lambda total, k: total % k))
print("fixed remainder:", count_runs_divisible(till, 5, remainder))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

prefix totals 0 4 -2 1 3 0
plain % remainders 0 4 3 1 3 0
plain %: 2
fixed remainder: 2

The same function in Java and TypeScript, run in each language, gives a different count with the plain %:

Stretches counted on 4 −6 3 2 −3 for k = 5, from a run in each language
Language	With the plain %	With ((s % k) + k) % k
Python	2	2
Java	1	2
TypeScript	1	2

The Java and TypeScript runs missed the stretch 3 2 with no error, because −2 and 3 are different keys. The pass is O(n) time and O(k) extra space, since the map holds at most k remainders. Writing the fixed form in Python too costs nothing and keeps the solution correct when it is translated.

← → move through sections and cards