Solutions

# Counting bits, Brian Kernighan's algorithm, DP
# bit,dp

# Bit counting: time O(n * log n), space O(1)
def countBits(n: int) -> list[int]:
    def countbits(i: int) -> int:
        count = 0
        for d in range(32):
            if i & (1 << d):
                count += 1
        return count

    bitcount = []
    for i in range(n+1):
        bitcount.append(countbits(i))

    return bitcount
    
# Brian Kernighan's algorithm: time O(n * log n), O(1) space
def countBits(n: int) -> list[int]:
    res = [0] * (n + 1)
    for i in range(1, n + 1):
        num = i
        while num != 0:
            res[i] += 1
            num &= (num - 1) # removes the lowest set bit
    return res
        
# DP: time O(n), space O(1)
def countBits(n: int) -> list[int]:
    dp = [0 for _ in range(n+1)]
    offset = 1

    for i in range(1, n+1):
        if i == 2 * offset: # change offset when i is a power of 2
            offset = i
        dp[i] = dp[i - offset] + 1

    return dp

# // one bit group
#  0=   0(0)
#  1=   1(1)
# // two bits group
#  2=  10(1) = 1 + (bit of -2)
#  3=  11(2) = 1 + (bit of -2)
# // three bits group
#  4= 100(1) = 1 + (bit of -4)
#  5= 101(2) = 1 + (bit of -4)
#  6= 110(2) = 1 + (bit of -4)
#  7= 111(3) = 1 + (bit of -4)
# // four bits group
#  8=1000(1)= 1 + (bit of -8)
#  9=1001(2) = 1 + (bit of -8)
# 10=1010(2) = 1 + (bit of -8)
# 11=1011(3) = 1 + (bit of -8)
# 12=1100(2) = 1 + (bit of -8)
# 13=1101(3) = 1 + (bit of -8)
# 14=1110(3) = 1 + (bit of -8)
# 15=1111(4) = 1 + (bit of -8)