Bit Manipulation
A recurrence over bit patterns
Counting for every number up to n, where doing each one separately is the obvious approach and a recurrence is better.
Key idea
Every number up to n, not just n
Counting the set bits of one number is the last lesson. Counting them for every number from zero to n invites doing that once per number, which is fine and does more work than necessary.
This is Unit 14 territory: if the answer for one input can be built from the answer for a smaller one, build it.
Why it works
Drop the lowest bit and look it up
Any number is its own value shifted right by one, with the lowest bit put back. Shifting right produces a strictly smaller number whose answer is already known.
So the count for n is the count for n right-shifted by one, plus one if n is odd. One lookup and one test, per number.
Tip
The fill order is free here
value >> 1 is always strictly less than value for positive values, so iterating upward guarantees the cell being read is already filled. No thought about ordering is required, which is unusual.
That is worth noticing because it is the same dependency question as every table in Units 14 and 15, and here it answers itself.
Key idea
A second recurrence, using the other identity
There is another route using the clear-the-lowest-set-bit identity from the last lesson: the count for n is one more than the count for n & (n - 1), since that value has exactly one fewer set bit.
Both are one line and both are linear. Knowing two recurrences for the same quantity is a good sign you understand it rather than remember it.
The value it reaches back to is different, and just as reliably smaller.
Cost
Cost
One pass with constant work per number, so O(n) time and O(n) space for the output.
The obvious approach counts bits individually, which is O(n log n) since each count takes about log n steps. Stating that gap explicitly is the point of the problem, because the naive version is otherwise perfectly reasonable.
Predict the output: the value each answer reaches back to
Two different recurrences for the same quantity are compared, by printing what each one reaches back to. Type the five lines it prints.
Counting Bits
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.