Question 338 Counting Bits

Link:

https://leetcode.com/problems/counting-bits/

 

My Code:

class Solution:
    def countBits(self, num: int) -> List[int]:
        if num == 0:
            return [0]
        else:
            Exponent = math.floor(math.log2(num))+1
            OutPutList = [0]

            for i in range(Exponent):
                NewList = [x+1 for x in OutPutList]
                OutPutList = OutPutList + NewList
            OutPutList = OutPutList[:(num+1)]
            return OutPutList

Explanation:

Notice that the there are changes occur at indices 2^i. Here we notice that, for for the number between 2^i and 2^i-1, the binary representation is 1xxxx(i numbers after 1), the number of ones in this range is 1 + all the numbers for the list from 0 to 2^i-1. Hence for we just find out all the possible exponents, and we first plus one for all the elements in the previous list, then we concatenate this list in the original list to obtain the list up to 2^i. Here we take one more because the number might not be exact the power of two. For the Last line, we take out the list we need and return it.