Counting Bits

---

Intuition

• Check whether the remainder is 1 after dividing by 2, and add that to res. Continue for each.
• Notice that the subproblems overlap. The next index i is simply that computed value, along with whatever was computed when divided by 2.

Complexity

Runtime

• $O(N)$

Space

• $O(N)$

Code

Dynamic Programming

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

Naive

class Solution:
    def countBits(self, n: int) -> List[int]:
        def countBinaryOnes(i):
            res = 0
            while i != 0:
                if i % 2 == 1:
                    res += 1
                i //= 2
 
            return res
        
        res = []
        for i in range(0, n + 1):
            res.append(countBinaryOnes(i))
        
        return res

Notes

Drive

Cards

START Basic Front: Counting Bits Back: remainder n % 2 1 ? 1 : 0 + dp of floor of n / 2 END

---

References

• Counting Bits