LC338. Counting Bits

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [-1] * (n + 1)
        res[0] = 0
        nearest2 = 0
 
        for v in range(1, n + 1):
            # Could also be `nearest2 * 2 == v`
            if v & (v - 1) == 0:
                nearest2 = v
                res[v] = 1
                continue
            
            subv = v - nearest2
            res[v] = 1 + res[subv]
        
        return res

Complexity

Time: $O(n)$
Space: $O(n)$