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.
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
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.