Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 <= i <= num calculate the number of 1's in their binary representation and return them as an array. Tags: Binary, Dynamic Programming

Try It!

Discussion

Video

Solution

class Solution:
    def countBits(self, num: int) -> List[int]:
        # numbers can be represented as 2n or 2n + 1
        # numBits(2n) == numBits(n)
        # numBits(2n + 1) == numBit(n) + 1
        
        dp = [0 for i in range(num + 1)]
        
        for i in range(1, num + 1):
            dp[i] = dp[i // 2] + (i % 2)
            # or with bit operators
            # dp[i] = dp[i >> 1] + (i & 1)
            
        return dp