Counting Bits from 0 to N

Problem

Return a list counts where counts[i] is the number of set bits in the binary representation of i, for every i from 0 through n.

Use the recurrence counts[i] = counts[i >> 1] + (i & 1) to compute each value in constant time. Return [0] for n = 0.

Hint

Dropping the lowest bit of i gives a smaller number whose popcount is already known.

case 1

in: [2]

expected: [0,1,1]

case 2

in: [5]

expected: [0,1,1,2,1,2]

case 3

in: [0]

expected: [0]

case 4

in: [10]

expected: [0,1,1,2,1,2,2,3,1,2,2]

Starter codePython

def count_bits_upto(n):
    # Your code here
    pass

4 test cases · run your code against them in the editor