Counting Bits – Solution & Complexity
Solution Walkthrough
1. Brute-force baseline
- For each number
i, repeatedly inspect or remove bits until the number becomes zero. - That works, but it repeats nearly the same work for neighboring numbers.
2. Reuse smaller answers
- Shifting
iright by one bit removes only the last bit. - So the answer for
iis the answer fori >> 1plus the removed bit.
3. Fill the DP from left to right
- Once
answer[0]is known, every later value depends only on an earlier index. - That makes a simple forward loop enough.
4. Final solution (all languages)
Dynamic programming over the previous half-value gives every popcount in linear time.
5. Complexity summary
- Time:
O(n). - Space:
O(n)for the returned array.
