Count the 1 bits in each of the numbers 0, 1, 2, ..., n and return the counts as an array, in that order. The array has n + 1 entries, and entry i is the count for the number i.
Example 1
Input
n = 8
Output
[0, 1, 1, 2, 1, 2, 2, 3, 1]
Explanation
0 to 8 in binary are 0, 1, 10, 11, 100, 101, 110, 111 and 1000, which hold 0, 1, 1, 2, 1, 2, 2, 3 and 1 one bits.
Example 2
Input
n = 0
Output
[0]
Explanation
the array still has n + 1 = 1 entry, and 0 has no 1 bits.
Constraints:
0 <= n <= 10^5
Follow-up: can you fill the whole array in O(n) time, without counting the bits of each number from scratch?
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.