NUHMAN.com

Introduction

LeetCode 338: Counting Bits asks you to return an array representing the number of 1's (set bits) in the binary representation of all numbers from 0 to n. The goal is to do this in linear time without using any built-in functions like bin() or bit_count().

This problem is a classic application of dynamic programming with bit manipulation, particularly focusing on understanding patterns in binary numbers.

Problem Statement

Given an integer n, return an array ans of length n + 1 such that ans[i] is the number of 1's in the binary representation of i.

Example

python

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 -> 0 => 0 ones  
1 -> 1 => 1 one  
2 -> 10 => 1 one  
3 -> 11 => 2 ones  
4 -> 100 => 1 one  
5 -> 101 => 2 ones

Approach 1: Dynamic Programming (using i & (i - 1))

This trick relies on a powerful bit manipulation property:

For any integer i, i & (i - 1) removes the lowest set bit from i.

For example:

• 5 (101) & 4 (100) = 100 → removes one 1
• Thus, countBits(5) = countBits(5 & 4) + 1 = countBits(4) + 1

This gives a DP recurrence relation:

dp[i] = dp[i & (i - 1)] + 1

This works because if we already know the number of 1s in i & (i - 1), then i has one more bit set.

✅ Python Code (Bit Manipulation + DP)

python

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i & (i - 1)] + 1
        return dp

🧠 Alternative Approach: Using Right Shift

Another way to see this:

• If i is even → its last bit is 0 → countBits(i) = countBits(i >> 1)
• If i is odd → its last bit is 1 → countBits(i) = countBits(i >> 1) + 1

python

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

🔎 Dry Run Example (n = 5)

iBinarydp[i]000001001120101301124100151012

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(n)

Each number from 0 to n is processed once, and we store one result per number.

🔥 Why This Works Well

• No bit-counting loops.
• Each result reuses previously computed results (pure DP).
• Much faster than naive approaches.

🧪 Edge Cases

InputOutputn = 0[0]n = 1[0, 1]n = 2[0, 1, 1]

✅ Conclusion

LeetCode 338: Counting Bits is an elegant use of bitwise operations combined with dynamic programming. It reinforces how understanding low-level operations can drastically improve performance and reduce complexity.

Whether you use i & (i - 1) or i >> 1, both approaches offer O(n) time and space complexity — perfect for interviews and performance-critical applications.