# 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