Counting Bits LeetCode solution in Python

1
class Solution:
2
    def countBits(self, n: int) -> List[int]:
3
        # We know that all exponential values of two have 1 bit turned on, the rest are turned off.
4
        # Now, we can find a relation with following numbers after 2, where the numbers can be decomposed
5
        # into smaller numbers where we already have found the # of 1s, for example.
6
        # F(3) = F(2^1) + F(1) = 1 + 1 = 3
7
        # F(4) = F(2^2) + F(0) = 1 + 0. ( Even thought we havent defined F(4) = F(2^2), by the previous established)
8
        # comment, we can safely say that all F(2^X) has only 1 bit so thats where F(4) would be = 1
9
        # F(5) = F(2^2) + F(1) = 1 + 1 = 2
10
        # F(6) = F(2^2) + F(2) = F(4) + F(2) = 1 + 1
11
        # The relation countinues for all following numbers
12

13
        # This solution is O(N)
14
        # With O(1) extra space ( considering dp is the returned answer )
15

16
        dp = [0]
17

18
        for i in range(1, n + 1):
19
            exponent = int(math.log(i) / math.log(2))
20
            num = 2**exponent
21
            decimal = i % (num)
22
            if num == i:
23
                dp.append(1)
24
            else:
25
                dp.append(dp[num] + dp[decimal])
26
        return dp