Count Bits for Every Number up to n
You get a non-negative integer n.
Return an array counts of length n + 1. For every i from 0 to n, counts[i] is the number of 1 bits in the binary form of i.
Hint
You can count the bits of each number on its own, but there is a faster way that reuses answers you already have. The number i >> 1 is i without its lowest bit. So counts[i] = counts[i >> 1] + (i & 1). This gives an O(n) solution.
Examples
Example 1
- Input:
- 0
- Output:
- [0]
Only the number 0, which has no 1 bits.
Example 2
- Input:
- 5
- Output:
- [0,1,1,2,1,2]
In binary: 0, 1, 10, 11, 100, 101. Their 1-bit counts are 0, 1, 1, 2, 1, 2.
Example 3
- Input:
- 9
- Output:
- [0,1,1,2,1,2,2,3,1,2]
7 is 111 (three 1 bits). 8 is 1000 (one 1 bit). 9 is 1001 (two 1 bits).
Constraints
0 <= n <= 256
Run checks your code against the 3 examples. Submit checks it against all 103 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.