very simple DP solution


  • 0
    S

    Logic: Number of bits for any element = 1 + bits for previous element. Reset to 1 for every 'n' that is power of 2 e.g 2, 4, 8, etc,.

        def countBits(self, nums):
            """
            :type num: int
            :rtype: List[int]
            """
            if nums == 0: return [0]
    
            dp = [0 for i in xrange(nums+1)]
            dp[1] = 1
            
            for i in xrange(1, nums+1):
                if i & (i-1) == 0:
                    curr = i
                    dp[i] = 1
                elif i%2 == 0:
                    dp[i] = 1 + dp[i-curr] 
                else:
                    dp[i] = 1 + dp[i-1]
            
            return dp[:nums+1]
    

Log in to reply
 

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