LeetCode 338: Counting Bits Solution in Python – A Step-by-Step Guide

What Is LeetCode 338: Counting Bits?

In LeetCode 338: Counting Bits, you’re given an integer n, and your task is to return an array of length n+1 where each element i contains the number of 1s in the binary representation of i. For example, with n = 5, the result is [0,1,1,2,1,2] (0:0, 1:1, 2:1, 3:2, 4:1, 5:2). This problem tests your ability to optimize bit counting, connecting to concepts in LeetCode 191: Number of 1 Bits.

Problem Statement

• Input: An integer n.
• Output: An integer array of length n+1 with the count of 1s in binary for each i from 0 to n.
• Rules:
• Compute Hamming weight (number of 1s) for each number.
• Array index i corresponds to number i.

Constraints

• 0 <= n <= 10⁵

Examples

• Input: 5
• Output: [0,1,1,2,1,2] (0:0, 1:1, 2:10, 3:11, 4:100, 5:101)
• Input: 2
• Output: [0,1,1] (0:0, 1:1, 2:10)
• Input: 0
• Output: [0] (0:0)

Understanding the Problem: Counting the 1s

To solve LeetCode 338: Counting Bits in Python, we need to compute the number of 1s in the binary form of each integer from 0 to n efficiently. A naive approach—counting bits for each number individually—is O(n * k), where k is the number of bits (≈32 for 10⁵), too slow for large n. Instead, we’ll use:

• Best Solution (DP with Bit Patterns): O(n) time, O(n) space—fast and elegant.
• Alternative Solution (Brute Force): O(n * log n) time, O(n) space—simple but less efficient.

Let’s start with the DP with bit patterns solution, explained in a beginner-friendly way.

Best Solution: DP with Bit Patterns

Why This Is the Best Solution

The DP with bit patterns approach is the top choice for LeetCode 338 because it’s highly efficient—O(n) time, O(n) space—and leverages a brilliant pattern: the number of 1s in a number can be derived from a smaller number by adding 1 if the least significant bit (LSB) is 1. It uses the formula dp[i] = dp[i >> 1] + (i & 1) to build the solution iteratively. It’s like spotting a rhythm in the bits—smart and quick!

How It Works

Think of this as a bit-building dance:

• Step 1: Initialize DP Array:
• dp[i] = number of 1s in binary of i.
• Base case: dp[0] = 0.
• Step 2: Use Pattern:
• For any i:
• Right shift i (i >> 1) gives i//2 (drops LSB).
• Add 1 if LSB is 1 (i & 1).
• E.g., 5 (101) = 2 (10) + 1 = dp[2] + 1.
• Step 3: Fill Array:
• Iterate from 1 to n, applying the formula.
• Step 4: Why It Works:
• Each number builds on a previous result.
• Bit manipulation avoids counting each bit.

It’s like counting bits with a clever shortcut!

Step-by-Step Example

Example: n = 5

• Init: dp = [0, 0, 0, 0, 0, 0]
• i=1 (1): dp[1] = dp[0] + (1 & 1) = 0 + 1 = 1
• i=2 (10): dp[2] = dp[1] + (2 & 1) = 1 + 0 = 1
• i=3 (11): dp[3] = dp[1] + (3 & 1) = 1 + 1 = 2
• i=4 (100): dp[4] = dp[2] + (4 & 1) = 1 + 0 = 1
• i=5 (101): dp[5] = dp[2] + (5 & 1) = 1 + 1 = 2
• Result: [0, 1, 1, 2, 1, 2]

Code with Detailed Line-by-Line Explanation

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

        # Fill array using pattern
        for i in range(1, n + 1):
            dp[i] = dp[i >> 1] + (i & 1)  # dp[i//2] + LSB

        return dp

• Line 3: Create array of size n+1, dp[0] = 0.
• Lines 6-7: Iterate 1 to n:
• i >> 1: Shift right (divide by 2).
• i & 1: Check LSB (0 or 1).
• dp[i] = dp[i//2] + LSB.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(n)—dp array.

This is like a bit-counting maestro—fast and sleek!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute-force approach—O(n * log n) time, O(n) space—counts 1s for each number by shifting and checking each bit individually. It’s the simplest way to understand bit counting but less efficient due to repeated bit operations. It’s like counting fingers on every hand—thorough but slow!

How It Works

Count bits one-by-one:

• Step 1: For each i from 0 to n:
• Shift right and check LSB until 0.
• Step 2: Sum 1s for each number.
• Step 3: Store in array.

Step-by-Step Example

Example: n = 3

• i=0: 0 (0) → 0
• i=1: 1 (1) → 1
• i=2: 10 (2) → 1
• i=3: 11 (3) → 2
• Result: [0, 1, 1, 2]

Code for Brute Force Approach

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

        def count_ones(num):
            count = 0
            while num:
                count += num & 1
                num >>= 1
            return count

        for i in range(n + 1):
            result[i] = count_ones(i)

        return result

• Time Complexity: O(n * log n)—log n shifts per number.
• Space Complexity: O(n)—result array.

It’s a bit-counting plodder—basic but heavy!

Comparing the Two Solutions

• DP with Bit Patterns (Best):
• Pros: O(n) time, O(n) space, fast and scalable.
• Cons: Requires pattern insight.
• Brute Force (Alternative):
• Pros: O(n * log n) time, O(n) space, straightforward.
• Cons: Slower due to bit-by-bit counting.

DP wins for efficiency.

Additional Examples and Edge Cases

• 0: [0].
• 1: [0, 1].
• 4: [0, 1, 1, 2, 1].

Both handle these, but DP is faster.

Complexity Breakdown

• DP with Bit Patterns: Time O(n), Space O(n).
• Brute Force: Time O(n * log n), Space O(n).

DP is the clear choice.

Key Takeaways

• DP with Bit Patterns: Pattern power—efficient!
• Brute Force: Count each—simple!
• Python: Bits and arrays shine—see [Python Basics](/python/basics).
• Bits: Patterns beat brute force.

Final Thoughts: Count the Bits

LeetCode 338: Counting Bits in Python is a bit-manipulation delight. The DP with bit patterns solution offers speed and elegance, while brute force provides a tangible baseline. Want more bit challenges? Try LeetCode 191: Number of 1 Bits or LeetCode 461: Hamming Distance. Ready to count? Head to Solve LeetCode 338 on LeetCode and tally those 1s today!