LeetCode 338. 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.
'''
'''
Solution;
when n = 2k: count(n) = n/2
when n = 2k+1: count(n) = count(n/2) +1
'''

#76ms, 16MB
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        if num == 0: return [0]
        elif num == 1: return [0,1]
       
        result = [0, 1]
        for i in range(2, num+1):
            if i%2 == 0:
                result.append(result[i/2])
            else:
                result.append(result[(i-1)/2]+1)
       
        return result