Skip to main content

🟩 Counting Bits (#338)

🔗 Problem Link​

📋 Problem Statement​

💡 Examples​

Example 1​

Input: n = 2
Output: [0,1,1]

Example 2​

Input: n = 5
Output: [0,1,1,2,1,2]

🔑 Key Insights & Approach​

Core Observation: dp[i] = dp[i >> 1] + (i & 1). Use previous results.

Why DP?

  • O(n) time, O(1) extra space
  • Reuse previous counts
  • i >> 1 removes rightmost bit

Pattern: "Bit DP" pattern.

🐍 Solution: Python​

Approach: DP with Bit Shift​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            dp[i] = dp[i >> 1] + (i & 1)

        return dp

🔵 Solution: Golang​

Approach: DP​

Time Complexity: O(n) | Space Complexity: O(1)

func countBits(n int) []int {
    dp := make([]int, n+1)

    for i := 1; i <= n; i++ {
        dp[i] = dp[i>>1] + (i & 1)
    }

    return dp
}

📚 References​