LC 0338 [E] Counting Bits - ALawliet/algorithms GitHub Wiki

a bit is just a power of 2

https://www.youtube.com/watch?v=RyBM56RIWrM&ab_channel=NeetCode

class Solution:
    def countBits(self, n: int) -> List[int]:
        offset = 1 # this will help to track highest pow(2,n) so far = most significant bit value ex: 1,2,4,8,16...

        T = [0] * (n + 1)
        
        for i in range(1, n + 1):
            if offset * 2 == i: # reach a new power of 2 = most significant bit
                offset = i
            T[i] = 1 + T[i - offset]
            
        return T

def countBits(self, num: int) -> List[int]:
    counter = [0]
    for i in range(1, num+1):
        counter.append(counter[i >> 1] + i % 2)
    return counter