Given an integer n, return a list of n + 1 numbers where item i is the number of 1 bits in
the binary form of i, for every i from 0 to n.
For example, 5 is 101 in binary, so item 5 is 2. Counting each number's bits one at a time
takes O(n log n) time; aim for O(n).
Example 1
- Input
- n = 2
- Output
- [0, 1, 1]
0, 1 is 1 and 2 is 10.Example 2
- Input
- n = 6
- Output
- [0, 1, 1, 2, 1, 2, 2]
11, 5 is 101 and 6 is 110: two 1s each.Constraints
- 0 ≤
n≤ 10⁴
Show the pattern
Bit manipulation
Shifting `i` right by one drops its last bit, so the count for `i` is the count for `i >> 1` (already worked out) plus that last bit, `i & 1`: bit operations turn it into one pass.
Show the approach
Build the list from 0 upwards. Shifting i right by one (i >> 1, the same as i // 2) drops
its last bit and keeps the rest, so i has as many 1 bits as i >> 1, plus one more when its
last bit, i & 1, is 1. Since i >> 1 < i for every i ≥ 1, that count is already in the list:
bits[i] = bits[i >> 1] + (i & 1).
Another rule works the same way: i & (i − 1) clears the lowest 1 bit of i, so
bits[i] = bits[i & (i − 1)] + 1.
Time: O(n) · Space: O(n) for the answer