338. Counting Bits

[fockspaces]

ans is an array that ans[i] is 1's counts for i's binary representation. we can list some of them: 0: 0 (0) 1: 1 (1) 2: 10 (1) 3: 11 (2) 4: 10 (1)

we found that,

1. if i % 2 == 0, we can directly make its value as ans[i // 2] since it just shift left 1 bit and append 0, 1's counts won't make change
2. if i % 2 != 0, that means it add 1 bit at the least bit comparing to i - 1, or we can also derive it from i // 2, just shit left and append 1 bit

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(n + 1):
            if i % 2 == 0:
                ans[i] = ans[i // 2]
            else:
                ans[i] = ans[i // 2] + 1
        return ans

[fockspaces]

we can further simplify the logic by removing if condition take advantage of i % 2 for determining whether add 1 or not.

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(n + 1):
            ans[i] = ans[i // 2] + i % 2
        return ans