aboutsummaryrefslogtreecommitdiff
path: root/counting_bits.py
blob: d9053efc2ab2463be42e249f9cffab5cdf4d2c0e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 338. Counting Bits

"""
given an integer 'n', return an array 'ans' of length 'n + 1' such that for
each 'i (0 <= i <= n)', 'ans[i]' is the number of 1's inthe binary
representation of 'i'
"""


class Solution(object):
    def countBits(self, n):
        cnt = [0]
        for i in range(1, n + 1):
            cnt.append(cnt[i >> 1] + i % 2)
        return cnt

if __name__ == "__main__":
    obj = Solution()
    print(obj.countBits(2)) # expect: 0 1 1
    print(obj.countBits(5)) # expect: 0 1 1 2 1 2