Count the Set Bits for Every Value up to a Limit
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Count the Set Bits for Every Value up to a Limit
Given a nonnegative integer `n`, return an array `ans` of length `n+1`. For every integer `i` from `0` through `n`, `ans[i]` must equal the number of `1` digits in the binary representation of `i`.
Do not use a built-in population-count function such as C++ `__builtin_popcount`.
### Function
`vector<int> countBits(int n)`
### Example 1
```text
Input: n = 8
Output: [0,1,1,2,1,2,2,3,1]
```
For example, `7` is binary `111`, while `8` is binary `1000`, so their counts are `3` and `1`.
### Example 2
```text
Input: n = 0
Output: [0]
```
### Constraints
- `0 <= n <= 100000`.
### Clarifications
The result includes both endpoints `0` and `n`. Count the binary digits equal to one, not the number of decimal digits or the bit length. The result for zero is zero.
### What a Strong Answer Covers
- Correct results for every required integer, including zero.
- Values on either side of a power of two.
- Why the computation is correct without a built-in population count.
- Time and storage, separating the returned array from additional state.
### Follow-up Questions
A separate bit scan for every integer takes `O(n log n)` time. Can you compute the whole array in `O(n)` time, possibly in a single pass?
Overview: Practice producing binary set-bit counts for every integer from zero through a limit. Respect the built-in-function restriction, include both endpoints, and justify whole-array complexity.