[LeetCode] 338. Counting Bits

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

A naive solution:

Time complexity = O (n * sizeof(integer))  

class Solution:
    def countBits(self, num: int) -> List[int]:
        def helper(n):
            result = 0
            while n:
                result += n & 1
                n >>= 1
            
            return result
        
        return [helper(n) for n in range(num+1)]

A DP solution:

class Solution:
    def countBits(self, num: int) -> List[int]:
        result = [0] * (num + 1)
        if num >= 1:
            result[1] = 1
            
            for i in range(2, num+1):
                if i & 1 == 0:
                    # if i is even number
                    result[i] = result[i//2]
                else:
                    # if i is odd number
                    result[i] = result[i//2] + 1
        
        return result