The problem
Given n, return an array whose element i is the number of 1 bits in i, for every i from 0 to n. Try to do it in a single pass.
Examples
01
- Input
n = 2
- Output
[0, 1, 1]
02
- Input
n = 5
- Output
[0, 1, 1, 2, 1, 2]
Constraints
- 0 ≤ n ≤ 10⁵
The idea
Shifting right by one (i >> 1) drops i’s last bit: 1101 becomes 110. So i has the same 1 bits as i >> 1, plus its own last bit, which is i & 1.
And i >> 1 is smaller than i, so its count is already in the array: ones[i] = ones[i >> 1] + (i & 1). For 5 (101): ones[2] (10, one bit) + 1 = 2.
- Time
- O(n)
- Space
- O(1) besides the answer
Solution · every language run against every case
class Solution: def countBits(self, n: int) -> List[int]: # i >> 1 is i without its last bit, and already counted; add that last bit back. ones = [0] * (n + 1) for i in range(1, n + 1): ones[i] = ones[i >> 1] + (i & 1) return ones