Yang Shuqi

Counting Bits

 

    338. Counting Bits

    Solution

    1. Use the characteristic of odd and even numbers, i.e. odd number end with 1 and even number end with 0.

    2. Can use num // 2 as memory.

    Reference

    def countBits(self, num):
    """
    :type num: int
    :rtype: List[int]
    """
    bitCountList = [0]

    for i in range(1, num + 1):
        bitCountList.append(bitCountList[i >> 1] + (i & 1))

    return bitCountList
    Search