Settlement blocks

A rooftop array meters every hour, positive when it draws from the grid and negative when it exports. The billing question is not what the total is, but how often a stretch of hours lands exactly on a block boundary.

The problem

A building's solar array logs one net figure per hour: positive kWh when the building imported, negative when it exported more than it used, zero when the two cancelled. The utility settles in whole blocks of block kWh, and an auditor wants to know how often the meter was already square — how many contiguous stretches of hours have a net total that is an exact multiple of block.

A stretch is a run of one or more consecutive hours, and two stretches differ if they start or end at different hours. A net total of zero counts.

Input. readings — a list of integers, the net kWh for each hour, possibly negative. block — a positive integer, the settlement block size.

Output. An integer, the number of contiguous stretches whose net total is divisible by block.

Example.

readings = [3, 1, 4, -3, 2], block = 4   ->  4

The four are hours 0-1 (3 + 1 = 4), hours 0-2 (8), hours 1-4 (1 + 4 - 3 + 2 = 4) and hour 2 alone (4).

A second example, where the negatives do the work:

readings = [-1, 2, 9, -5, 3], block = 3   ->  4

Hours 1-3 total 6, hours 1-4 total 9, hour 2 alone is 9, hour 4 alone is 3. The leading -1 never begins a settling stretch.

Constraints.

• 0 <= len(readings) <= 3 x 10^4
• -10^4 <= readings[i] <= 10^4
• 1 <= block <= 10^4

Hints

Approach

Brute force

Fix a start hour, extend the end hour, keep a running total, test each for divisibility. That is n(n + 1) / 2 totals — about 4.5 x 10^8 additions at the top of the constraints, too slow for a year of meter data.

The insight

Two prefixes with the same remainder mod block bracket a stretch that settles, so the answer is the number of pairs of equal remainders — countable in one pass with a tally.

Write P[k] for the total of the first k hours. Hours i to j sum to P[j+1] - P[i], which is divisible by block exactly when the two leave the same remainder. The precondition is that only the remainder matters and never the size of the prefix, which collapses n distinct totals into at most block buckets. Seeding remainder 0 with a count of 1 covers stretches starting at hour 0.

Algorithm

1. Start a tally holding remainder 0 with count 1, and a running total of 0.
2. For each hour, add its reading to the running total and reduce mod block.
3. Add the tally's current count for that remainder to the answer — every earlier prefix with the same remainder closes a settling stretch here.
4. Increment the tally for that remainder and continue.

Complexity

Time O(n) — one addition, one lookup and one increment per hour. Space O(min(n, block)) — the tally never holds more than block distinct remainders.

Solution

"""Settlement blocks — count prefix sums that share a remainder."""


def solve(readings, block):
    # Two prefix sums with the same remainder mod `block` bracket a stretch whose
    # net total is divisible by `block`. So the answer is the number of pairs of
    # equal remainders, counted as we go.
    seen = {0: 1}                     # the empty prefix, remainder 0, exists once
    running = 0
    total = 0
    for kwh in readings:
        running = (running + kwh) % block   # Python keeps this in [0, block)
        # invariant: seen[r] counts prefixes before this hour with remainder r,
        # and every one of them closes a valid stretch ending at this hour.
        total += seen.get(running, 0)
        seen[running] = seen.get(running, 0) + 1
    return total

TESTS = [
    (([3, 1, 4, -3, 2], 4), 4),
    (([-1, 2, 9, -5, 3], 3), 4),
    (([7, -4, 6], 1), 6),
    (([1, 1], 5), 0),
    (([0], 7), 1),
    (([6, -6, 12], 6), 6),
    (([], 3), 0),
]

Pitfalls

• Forgetting the seed. Without remainder 0 -> count 1, every stretch that begins at hour 0 is missed: the first example drops to 2.
• A % that follows the sign of the dividend. A running total of -4 with block = 3 must key on 2, not -1, or one bucket splits in two. Python already does this; many languages do not.
• Counting after the increment. Adding the current prefix to the tally before reading it counts an empty stretch at every hour, inflating the answer by n.
• Storing prefix totals instead of remainders. Those keys only find stretches summing to zero, never to 2 x block.

Variants

• Bracket through the archive — a running total as a key again, read for its biggest bucket.
• Matched pledges — the same look-before-you-insert order, on a complement instead of a remainder.