Counting Bits – Solution & Complexity
Solution Walkthrough
Step 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.
- For each number
Step 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.
- Shifting
Step 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.
- Once
Step 4: Final solution (all languages)
Dynamic programming over the previous half-value gives every popcount in linear time.
Step 5: Complexity summary
- Time:
O(n). - Space:
O(n)for the returned array.
- Time:
