Counting Bits (Leetcode 338)

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

class Solution:
    def countBits(self, n: int) -> List[int]:
        
        # X =        7     -> 111   (3 1s)
        # Y = 7//2 = 3     -> 011   (2 1s)
        # Diff b/w 1s in bin(X) and bin(Y) is == 1
        
        # X =        12     -> 1100 (2 1s)
        # Y = 8//2 = 6     -> 110   (2 1s)
        # Diff b/w 1s in bin(X) and bin(Y) is == 0
        
        # The result depends upon X. 
        # If X is even, both X and Y have same number of 1s
        # If Y is odd, X has one 1 greater than Y
        
        dp=[0 for i in range(n+1)]
        dp[0]=0
        if(n==0):
            return dp
        dp[1]=1
        if(n==1):
            return dp
        for i in range(2,n+1):
            if(i%2==0):
                val=dp[i//2]
            else:
                val=dp[i//2]+1
            dp[i]=val
                
        return dp