Python DP - Exceedingly Simple To understand


  • 0

    If the integer is even, then its bits will be the same as itself halved.

    0110 (6)'s number of bits is same as 0011 (3)
    

    If it's odd, we add one to the result since to move from even to odd we just need to flip the 1 bit.

    def countBits(self, n):
        dp = [0 for i in range(n+1)]
        for i in range(1, n+1):
            if i % 2 == 0:
                dp[i] = dp[i/2]
            else:
                dp[i] = dp[i-1] + 1
        return dp
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.