Counting Bits — The Locker Stencils

Boss 3: The Locker Stencils

Boss 2 taught you to count the 1s in one number by striking bits with x & (x - 1). This boss asks the obvious follow-up: count them for every number from 0 to n. Run the old weapon n times and you'll win, slowly. But this is a crossover boss. It stands in the doorway between Dungeon 17 and Dungeon 12, and it only truly falls when a shift and a memo table shake hands.

The story

The school got new lockers over the summer, numbered 0 through n. Some administrator with strong opinions decided the numbers should be stenciled in binary, so locker 6 reads 110 and locker 13 reads 1101.

The painter is fine with this. His pricing is not subtle: he charges per 1-digit painted. Zeros are free, ones cost. So locker 7, stenciled 111, costs three units. Locker 8, stenciled 1000, costs one.

The clerk in the front office needs a bill list: for every locker from 0 to n, how many 1s did the painter charge for? She starts squinting at locker numbers, tallying ones digit by digit, and after twenty lockers her eyes hurt.

Then one of the painting crew leans on his roller and says something that ends the whole ordeal:

"Ma'am, we don't paint these from scratch. Locker 6 is locker 3's stencil with one more digit glued on the end. Half the work's already on the wall."

The problem, dressed up properly

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i, for every i from 0 to n.

LeetCode 338, "Counting Bits". The official follow-up dares you to do it in O(n) total, not O(n log n), and that dare is the entire boss.

The naive attempt

You own a perfectly good popcount from Boss 2. Point it at every locker:

def count_bits(n: int) -> list[int]:
    def ones(x: int) -> int:      # Boss 2's weapon, Kernighan's trick
        c = 0
        while x:
            x &= x - 1            # strike the lowest 1
            c += 1
        return c
    return [ones(i) for i in range(n + 1)]

This works. Each call costs one strike per set bit, so the total is O(n · k) where k is up to about log n bits. Nobody fails an interview for it.

But it's wasteful in a very specific, very familiar way. Counting the ones in 1101 involves counting the ones in 110, which involves counting the ones in 11, and we already computed all of those for earlier lockers. The subproblems overlap.

Overlapping subproblems. If that phrase rings a bell shaped like Dungeon 12, good. That bell is the whole fight.

The weapon: glue one digit onto a smaller bill

Take any number and shift it right by one: i >> 1. That drops the last binary digit and nothing else. So the binary of i is exactly the binary of i >> 1 with one digit appended, and that appended digit is i & 1, the last bit.

Now read that as a bill. The 1s in locker i split cleanly into two piles: the 1s in everything except the last digit, which is precisely locker i >> 1's bill, already sitting in the ledger because i >> 1 is smaller than i, plus the last digit itself, which is 1 or 0.

count[i] = count[i >> 1] + (i & 1)

That's the crossover. The recurrence structure, "answer for i comes from an already-stored smaller answer", is pure Dungeon 12 dynamic programming. The parent relation itself, which smaller answer to reach for, comes from a bit shift. DP supplies the ledger, bits supply the family tree.

def count_bits(n: int) -> list[int]:
    count = [0] * (n + 1)              # locker 0 is free: no 1s in 0
    for i in range(1, n + 1):
        count[i] = count[i >> 1] + (i & 1)
    return count

One line of real work per locker. And Boss 2's weapon has a cameo here too: i & (i - 1) clears the lowest set bit, which is also a number smaller than i with exactly one fewer 1. So this recurrence is equally valid:

        count[i] = count[i & (i - 1)] + 1

Same fight, different parent pointer. The shift version says "my bill is my parent's bill plus my last digit". The Kernighan version says "my bill is one more than the number that's me with my cheapest 1 scraped off". Both are O(n) total, pick whichever you can re-derive under pressure.

Watching it work

The ledger for n = 8, filled left to right:

Every row reaches back to a row already written. Locker 6 leans on locker 3, exactly as the crew guy said, and locker 3 leaned on locker 1 before that. No number is ever counted twice.

Gotchas

1. Mishandling locker 0. Seed count[0] = 0 and start the loop at 1. Run the recurrences at i = 0 and things get quietly ugly: the Kernighan form computes 0 & (0 - 1), which is 0 & -1, which is 0, then adds 1, billing locker 0 for a digit that was never painted. And a misremembered count[i - 1] variant reads count[-1] in Python, which doesn't crash, it silently reads the end of the list. Zero is the base case. Treat it like one.

2. Sweating i // 2 versus i >> 1. For the non-negative numbers on these lockers they are the same operation: floor-dividing by 2 and shifting right both drop the last binary digit, nothing more. Use whichever reads better. The distinction only matters for negative numbers in some languages, and no hallway has locker -5.

3. Recounting instead of reusing. Calling bin(i).count("1") or fresh Kernighan per locker gives O(n log n)-ish work and passes the judge, so people ship it and move on. The follow-up exists precisely to catch this. If your loop body contains another loop over bits, you've brought Boss 2's weapon to Boss 3's fight.

4. The highest-power variant and its trap. A third recurrence exists: count[i] = count[i - offset] + 1, where offset is the largest power of two at most i (subtracting it strips the leading 1). It works, but you must bump offset exactly when i reaches offset * 2. Forget that update and every count after the miss inherits the wrong parent. The shift version has no such moving part, which is why it's the one to memorize.

Complexity

One pass, constant work per locker, answers stored as we go.

Time: O(n). Space: O(n) for the output ledger, O(1) beyond it.

Boss down

The clerk fills the bill list in one walk down the hallway, never counting a digit twice, and the painter gets paid before lunch. The lesson travels well beyond lockers: numbers are not isolated strangers. Each one is a smaller number wearing one extra digit, and any per-number quantity that respects that gluing can be built for an entire range at once.

Next up, Boss 4: Reverse Bits — The Backwards Banner. A parade banner printed as a 32-bit word gets hung mirror-backwards, and you're asked to flip the whole thing end for end. Bit-by-bit works, but the real prize is the swap trick: halves, then quarters, then pairs, the entire word reversed in five moves. Bring a mirror.