338. Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example:

Input: n = 5             Output: [0,1,1,2,1,2]
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

def countBits(n: int):

       

    bitCounts = [0]*(n+1)    

           

    base = 1

    nextPowerOfTwo = 1

    while base <= n:

        for i in range(nextPowerOfTwo):

            if base + i > n:

                break

            bitCounts[base+i] = bitCounts[i] + 1

            i += 1

       

        base = base + nextPowerOfTwo

        nextPowerOfTwo = nextPowerOfTwo << 1

       

    return bitCounts