Counting Bits

Problem: Counting Bits

After observing and thinking, we can get that the number of bit 1 bases on all the previous results.

For example:

[0] -> 0

[0] + [1] -> 0, 1

[0, 1] + [1, 2] -> 2, 3

[0, 1, 1, 2] + [1, 2, 2, 3] -> 4, 5, 6, 7

Code in Python:

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        length, index, res = 1, 0, [0]
        for i in xrange(1, num+1):
            if index < length-1:
                res.append(res[index]+1)
                index += 1
            else:
                res.append(res[index]+1)
                length = len(res)
                index = 0
        return res