Counting Bits
Return set-bit counts for every integer from 0 through n.
Why does this pattern fit?
Restate the exact job
Return set-bit counts for every integer from 0 through n.
Removing the lowest set bit reaches a smaller number already solved.
O(n) time · O(n) output
Calling a full bit counter for each value adds an unnecessary log factor.
How to solve Counting Bits
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Return set-bit counts for every integer from 0 through n.
Why Bit manipulation fits
Removing the lowest set bit reaches a smaller number already solved.
State to maintain
dp[0..n].
Transition
Set dp[i]=dp[i & (i−1)] + 1.
Time and space
O(n) time · O(n) output
Counterexample to the tempting mistake
Calling a full bit counter for each value adds an unnecessary log factor.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.