Counting Bits
EasyBit Manipulation
Given a non-negative integer n, return a list ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n inclusive.
A per-number bit count gives O(n log n); aim for O(n) total by reusing answers you have already computed.
Example 1
- Input:
- n = 6
- Output:
- [0,1,1,2,1,2,2]
- Explanation
- In binary, 0 through 6 are
0,1,10,11,100,101,110. Counting the 1s in each gives 0, 1, 1, 2, 1, 2, 2.
Example 2
- Input:
- n = 0
- Output:
- [0]
- Explanation
- The range 0 through
nis inclusive, son = 0still produces one entry: 0 has no 1 bits.
Constraints
0 <= n <= 10^5