Counting Bits

LeetCode Counting Bits (Problem 338) gives you a non-negative integer n and asks you to return an array ans of length n + 1 where ans[i] is the number of 1-bits in the binary representation of i.

For example, if n = 5, you return [0, 1, 1, 2, 1, 2]. The entry at index 3 is 2 because 3 in binary is 011, which has two 1s. The entry at index 4 is 1 because 4 in binary is 100, which has one 1.

The naive approach would be to call a popcount function on every number from 0 to n. That works, but you can do something more interesting: build each answer from a previously computed one, visiting each number exactly once.

The key recurrence

Right-shifting a number by one position drops its least significant bit (LSB). So i >> 1 is i with its rightmost bit removed. That means the binary representation of i >> 1 differs from i by exactly one bit: the one you just dropped.

This gives you a free relationship:

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

i >> 1 is always less than i, so its popcount is already in your array by the time you need it. You look it up in O(1), then check whether the bit you dropped was a 1 (using i & 1). If the LSB was 1, you add one. If it was 0, you add nothing.

A few examples to make it concrete:

• bits[6]: 6 in binary is 110. 6 >> 1 = 3 (binary 11). 6 & 1 = 0 (even). So bits[6] = bits[3] + 0 = 2 + 0 = 2.
• bits[7]: 7 in binary is 111. 7 >> 1 = 3 (binary 11). 7 & 1 = 1 (odd). So bits[7] = bits[3] + 1 = 2 + 1 = 3.
• bits[4]: 4 in binary is 100. 4 >> 1 = 2 (binary 10). 4 & 1 = 0 (even). So bits[4] = bits[2] + 0 = 1 + 0 = 1.

Every even number has a 0 in its LSB, so you just inherit the count from i >> 1. Every odd number has a 1 in its LSB, so you add one to the count of i >> 1.

Alternative recurrence

There is a second valid recurrence worth knowing:

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

i & (i - 1) clears the lowest set bit of i. That gives you the same number with one fewer 1-bit, and since it is also less than i, it has already been computed. You always add 1 because you are accounting for the bit you cleared.

For example, bits[6]: 6 & 5 = 110 & 101 = 100 = 4. So bits[6] = bits[4] + 1 = 1 + 1 = 2.

Both recurrences produce identical results. The right-shift version (i >> 1) is slightly more common in practice because it works the same way for all numbers without needing the i - 1 subtraction.

The solution

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

You allocate the output array with all zeros. Index 0 is already correct (bits[0] = 0, since zero has no set bits). Then you sweep from 1 to n, filling each slot using the already-filled slot at i >> 1. The whole thing is a single pass.

Step-by-step walkthrough

Here is how the array fills in for n = 7. Watch how each cell pulls its value from an earlier cell.

Notice the pattern: whenever i is a power of two, bits[i] resets to 1. That is because powers of two have exactly one set bit in binary, and i >> 1 for a power of two is the previous power of two (which also has one set bit), but the LSB is 0 so you add 0 and inherit 1. Wait, more precisely: bits[4] = bits[2] + 0 = 1, bits[2] = bits[1] + 0 = 1, bits[1] = bits[0] + 1 = 1. The chain all the way back to the base case.

Complexity

The loop runs exactly n times. Each iteration does a right-shift, a bitwise AND, an addition, and an array lookup, all O(1). The output array has n + 1 entries, which is the required space. There is no extra data structure beyond what you return.

Building blocks

Right-shift to drop the LSB. i >> 1 in integer arithmetic is the same as floor division by 2. It removes the least significant bit. This is what lets you express bits[i] in terms of a smaller number.

Bitwise AND to test the LSB. i & 1 checks whether i is odd. If the result is 1, the LSB was set. If the result is 0, the LSB was 0. This single-bit mask is one of the most frequently used primitives in bit manipulation.

DP on already-computed subproblems. The pattern here is exactly the same as in classic DP: define a recurrence, guarantee that required subproblems are solved before the current one, and fill a table in order. You do not need memoization or recursion because the traversal order (0 to n) naturally satisfies the dependency.

Edge cases

n = 0: The loop body never executes. You return [0]. Zero in binary has no 1-bits.

n = 1: The loop runs once for i = 1. bits[1] = bits[0] + 1 = 1. You return [0, 1].

Powers of two: Every power of two has exactly one set bit. bits[1] = 1, bits[2] = 1, bits[4] = 1, bits[8] = 1, and so on. Right-shifting a power of two gives you the previous power of two, and since powers of two are even (except 1), the LSB is always 0 until you reach 1, which has LSB 1. The chain resolves cleanly.

Large n: The algorithm scales linearly. For n = 100000, you still do exactly 100000 iterations with O(1) work each.

From understanding to recall

Understanding why the recurrence works is one thing. Producing it from memory under interview pressure is another. The gap between those two is what spaced repetition closes.

The recall cue you want to lock in: "right-shift gives me a smaller number whose popcount I already know; the LSB tells me whether to add one more." If you can retrieve that sentence automatically, the code follows immediately.

Drill this problem a few times, spaced out over days. Each rep should be a cold-start: open a blank editor, write the solution from scratch without looking anything up, then compare. The reps get faster, and the pattern gets locked.

Related posts

• Number of 1 Bits - Counts the set bits in a single number using the n & (n-1) trick. Counting Bits is the batch version of this same idea, but uses DP instead of repeatedly clearing bits.
• Single Number - Uses XOR to cancel out paired elements. Another problem where a single bitwise primitive does all the heavy lifting.
• Power of Two - Tests whether a number has exactly one set bit using n & (n-1). Powers of two appear as the reset points in the Counting Bits output, each contributing a count of 1.