Count the 1 bits from 0 to n
For every whole number from 0 up to n (n is 0 or more), count the 1s in its binary form. Return those counts as a list counts in that order, so the list has n + 1 items and the item at position i is the count for i.
Binary is base 2: each digit, called a bit, is 0 or 1 and is worth a power of two, 1, 2, 4, 8 and so on from the right. 6 is 110 in binary (4 + 2), so counts[6] is 2.
Counting the bits of each number on its own is correct and passes the tests. Aim for one step per number by reusing a count you have already found.
n = 4Output[0, 1, 1, 2, 1]0 to 4 in binary are 0, 1, 10, 11 and 100, with 0, 1, 1, 2 and 1 ones.
n = 7Output[0, 1, 1, 2, 1, 2, 2, 3]5 is 101 and 6 is 110, two 1s each. 7 is 111, three 1s.
n = 0Output[0]One number, 0, with no 1s.
0 ≤ n ≤ 105
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.