Counting Bits
Build bits[0..n] in O(n) by reusing bits[i >> 1] instead of recomputing each popcount from scratch.
Open on LeetCode ↗Intuition
The obvious move is to run a popcount routine on every number from 0 to n independently, which is O(n log n) and, worse, throws away information you already have. Look at what shifting i right by one does: it drops the last bit and gives you a strictly smaller index that you have already solved. So bits[i] = bits[i >> 1] + (i & 1) -- the count of the smaller number plus whatever bit got shifted off the bottom. This turns the whole table into one linear pass where each answer is built from an earlier answer instead of recomputed from nothing. The invariant is that i >> 1 is always strictly less than i for i > 0, so by the time you need it, it is already filled in.
i >> 1 drops the last bit, so i has the same set bits as i / 2 plus its own final bit. That gives bits[i] = bits[i >> 1] + (i & 1) — every answer reuses one already computed, making the whole array linear.
Approach
Set bits[0] = 0
Zero has no set bits, which is the base case the recurrence builds on.
For each i from 1 to n, reuse bits[i >> 1]
Right-shifting i by one bit drops its lowest bit and yields i >> 1, an index smaller than i that has already been filled in during this same pass. That value already holds the correct popcount for the number with the last bit removed.
Add back the dropped bit
Set bits[i] = bits[i >> 1] + (i & 1). The (i & 1) term is exactly the bit that the shift discarded, so adding it restores the full count for i without ever counting bits from scratch.
Solution & live demo
Common pitfalls
Counting each number independently
bits[i] = bin(i).count('1')bits[i] = bits[i >> 1] + (i & 1)
That's O(n log n) and ignores the overlap between answers. Since i >> 1 < i, its count is already stored — one array read replaces the whole popcount.
Using i - 1 as the subproblem
bits[i] = bits[i - 1] + 1
bits[i] = bits[i >> 1] + (i & 1)
Consecutive integers have no simple bit-count relationship — 7 has three set bits and 8 has one. Halving is the operation with a clean recurrence.
Sizing the array to n
bits = [0] * n
bits = [0] * (n + 1)
The output covers 0 through n inclusive, which is n + 1 entries. Sizing to n drops the final answer and throws on the last write.
Edge cases
Result is just [0]; the loop from 1 to n never runs.
i >> 1 has no set bits contributed beyond the trailing 1 that gets added back, so bits[i] = 1, correctly matching a single set bit.
(i & 1) is 1 for odd i and 0 for even i, which is exactly whether the dropped bit was set.
Still O(n) total work and O(n) space for the output array; no per-number popcount loop is ever run.