Counting Bits
Easy
LC #338
bit manipulationdynamic programmingNot attempted yet
Given n, return a list ans of length n + 1 where
ans[i] is the number of 1 bits in i.
Can you do it in O(n), reusing earlier answers?
Example 1
Input: n = 2
Output: [0, 1, 1]
0 → 0, 1 → 1, 10 → 1
Example 2
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Example 3
Input: n = 8
Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]
Constraints
- 0 ≤ n ≤ 10⁵