Counting Bits

K Closest Points to Origin

Return the number of set bits for every integer from 0 through n.

Given a non-negative integer `n`, return an array `answer` where `answer[i]` is the number of `1` bits in the binary representation of `i` for every `0 <= i <= n`.

**Input / output**
- Input: `n: int`
- Output: `int[]` of length `n + 1`

**Examples**
1. `n = 2` returns `[0,1,1]`.
   `0` has zero set bits, `1` has one, and `2` (`10` in binary) also has one.
2. `n = 5` returns `[0,1,1,2,1,2]`.
   `3` is `11` and `5` is `101`, so both contribute two set bits.
3. `n = 0` returns `[0]`.
   The range still includes zero itself.

**Constraints**
- `0 <= n <= 10^5`

**Edge cases**
- `n` can be zero.
- The answer must include every value from `0` through `n` in order.

**Target complexity**
- Aim for `O(n)` time and `O(n)` output space.

**Hints**
1. `i >> 1` drops the least significant bit of `i`.
2. The bit count of `i` equals the bit count of `i >> 1` plus the final bit `i & 1`.

**Follow-up**
Can you derive the same recurrence using `i & (i - 1)` instead?

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

Brute-force baseline

- Shifting `i` right by one bit removes only the last bit.
- So the answer for `i` is the answer for `i >> 1` plus the removed bit.

Reuse smaller answers

- Once `answer[0]` is known, every later value depends only on an earlier index.
- That makes a simple forward loop enough.

Fill the DP from left to right

Dynamic programming over the previous half-value gives every popcount in linear time.

Final solution (all languages)

- Time: `O(n)`.
- Space: `O(n)` for the returned array.