How do you count contiguous runs whose total is divisible by k using prefix totals?

## The setup A warehouse ledger records signed weight adjustments per shipment line — dispatches positive, returns negative — and you want to count contiguous runs whose net weight is an exact multiple of the pallet size `k`, because those runs load cleanly. ## From exact totals to remainder classes Start from the identity: the run covering entries `l..r` totals `P[r+1] - P[l]`, where `P` is the running total. That difference is divisible by k exactly when ``` P[r+1] mod k == P[l] mod k ``` So instead of asking "which earlier positions had this exact total", you ask "which earlier positions had this REMAINDER". The map key changes; nothing else does. The scan is the familiar one. Keep a running total, reduce it mod k, add the bucket's current count to the answer, then increment the bucket. Seed the remainder-0 bucket with a count of one — the empty prefix has total 0, remainder 0, and is what makes runs starting at the first entry countable. ## What the key change buys Space drops from O(n) to O(min(n, k)): there are only k possible remainders, so a pallet size of 8 means eight buckets no matter how many million ledger lines you stream. When k is small and known, an indexed table of k counters replaces the hash map outright — no hashing, contiguous memory, and the same asymptotics with a much better constant. It also hands you a free existence proof. There are n+1 running totals including the empty prefix, dropped into k buckets, so as soon as n >= k the pigeonhole principle guarantees at least two share a bucket — meaning any ledger of at least k entries CONTAINS a run divisible by k. Interviewers like that observation because it shows you reasoned about the structure rather than only coding the scan. ## The remainder trap, which is the real question Remainder operations do not agree on sign across environments. Some define the result to follow the sign of the dividend, so reducing a negative running total yields a negative remainder; others always return a value in `[0, k)`. Under the sign-following rule, a running total of -2 with k = 5 keys the bucket `-2`, while a running total of +3 — congruent to it, since -2 and 3 differ by 5 — keys the bucket `3`. One congruence class, two buckets, and the pairs that should have matched never do. The output is an undercount that appears only when the data contains negatives, which is exactly the case a positive-only test set never exercises. The fix is one expression applied to every key before it reaches the map: ``` key = ((sum mod k) + k) mod k ``` The first reduction lands in `(-k, k)`, adding k lifts it non-negative, and the second reduction brings it back into `[0, k)`. Applying it unconditionally costs nothing and removes the environment dependence entirely, which is why it belongs in the code rather than in a comment about which behaviour you assume. ## Edge cases to state - k = 0 is not a valid pallet size; guard it, since a remainder by zero is undefined. - Negative k should be normalised to its absolute value before bucketing; divisibility does not care about the sign of the divisor, but bucket indices do. - The running total can still overflow a fixed-width accumulator on a long ledger even though the KEYS stay small. Reducing the running total mod k as you go — rather than accumulating the raw total and reducing at the end — keeps the accumulator bounded and is worth mentioning. ## Counting versus longest, again The two bookkeeping styles carry over unchanged. To COUNT runs, store a frequency per remainder bucket and increment on every visit. To find the LONGEST run divisible by k, store the earliest index per remainder, write only when the bucket is empty, and seed remainder 0 with index -1. Same identity, same single pass, different value in the bucket. ## What a weak answer looks like "Check every run's total against k" — that is the quadratic scan the pattern replaces. "Use the running total itself as the key" — that finds runs totalling exactly zero, a strictly narrower question. "Remainders are always non-negative" — assuming that is exactly the defect this question exists to expose.