Counting Bits

LeetCode 338: Counting Bits Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes dynamic programming to generate bit counts in $O(n)$ time by reusing the count of set bits from the number i / 2.

The LeetCode 338 problem, titled Counting Bits, asks us to compute the number of 1s (set bits) in the binary representation for every integer from 0 to n. Instead of returning a single value, we must return an array of length n + 1 where the index i stores the population count (Hamming weight) of the integer i.

This is a fundamental problem for understanding how bitwise operations can be combined with dynamic programming to optimize runtime from superlinear to linear.

Brute Force Approach for Counting Bits

The most straightforward way to solve this problem is to iterate through every number from 0 to n and count the bits for each number individually.

For a specific integer k, we can count bits by repeatedly checking the least significant bit (LSB) and right-shifting the number until it becomes 0.

Pseudo-code:

function countBits(n):
    result = []
    for i from 0 to n:
        count = 0
        num = i
        while num > 0:
            if num is odd:
                count = count + 1
            num = num >> 1
        result.append(count)
    return result

Why this fails (or is suboptimal): While this approach produces the correct result, it performs redundant calculations. The time complexity is $O(n \cdot \log n)$ because counting bits for a number $i$ takes $O(\log i)$ time (proportional to the number of bits). The problem specifically requests a linear time solution, $O(n)$. In a strict interview setting, the brute force approach demonstrates a lack of insight into the relationship between binary representations of consecutive or related numbers.

Algorithm Strategy: Bit Manipulation Patterns

We implement this using a single pass Dynamic Programming approach.

1. State Definition: Let ans be an array of size n + 1. ans[i] represents the number of set bits in the integer i.
2. Base Case: ans[0] = 0. The number 0 has zero set bits.
3. Recurrence Relation: For every $i$ from 1 to $n$, calculate ans[i] using the value stored at ans[i >> 1] (which is ans[i // 2]).
   • ans[i] = ans[i >> 1] + (i & 1)
4. Iteration: Iterate linearly from 1 to $n$. Since i >> 1 is strictly less than i, the value needed for the calculation is guaranteed to be available in the ans array.

This strategy ensures we strictly satisfy the $O(n)$ time complexity constraint and use no built-in bit counting functions.

Execution Flow

Let's trace the algorithm for n = 5. We initialize ans array of size 6 with ans[0] = 0.

1. i = 1 (Binary 1):

   • Calculate 1 >> 1 which is 0.
   • Check LSB 1 & 1 which is 1.
   • ans[1] = ans[0] + 1 => 0 + 1 = 1.
   • Array: [0, 1, ...]

2. i = 2 (Binary 10):

   • Calculate 2 >> 1 which is 1.
   • Check LSB 2 & 1 which is 0.
   • ans[2] = ans[1] + 0 => 1 + 0 = 1.
   • Array: [0, 1, 1, ...]

3. i = 3 (Binary 11):

   • Calculate 3 >> 1 which is 1.
   • Check LSB 3 & 1 which is 1.
   • ans[3] = ans[1] + 1 => 1 + 1 = 2.
   • Array: [0, 1, 1, 2, ...]

4. i = 4 (Binary 100):

   • Calculate 4 >> 1 which is 2.
   • Check LSB 4 & 1 which is 0.
   • ans[4] = ans[2] + 0 => 1 + 0 = 1.
   • Array: [0, 1, 1, 2, 1, ...]

5. i = 5 (Binary 101):

   • Calculate 5 >> 1 which is 2.
   • Check LSB 5 & 1 which is 1.
   • ans[5] = ans[2] + 1 => 1 + 1 = 2.
   • Array: [0, 1, 1, 2, 1, 2]

The final output is [0, 1, 1, 2, 1, 2].

Proof of Correctness

The correctness relies on the inductive property of the integers.

• Base Case: For $i=0$, the number of bits is 0. The array is initialized correctly.
• Inductive Step: Assume that for all $k < i$, ans[k] correctly contains the bit count of $k$.
  • Consider $i$. The value i >> 1 (integer division by 2) is strictly less than $i$ for all $i > 0$. Therefore, ans[i >> 1] is already computed and correct by our assumption.
  • The binary representation of $i$ consists of the bits of $i >> 1$ shifted to the left, plus the LSB of $i$.
  • Therefore, the count of set bits in $i$ is strictly the count of set bits in $i >> 1$ plus the LSB.
  • The formula ans[i >> 1] + (i & 1) captures this logic perfectly.

Pattern Reuse Notes

The Bitwise DP pattern and the specific logic used here (relating a number to its shifted version) is useful in several other scenarios:

• Reverse Bits: Understanding how bits shift is crucial for reversing bits in $O(1)$ or $O(\log n)$ steps.
• Integer Replacement: Problems involving transforming integers using operations like division by 2 often utilize similar recursive structures or bitwise logic.
• Gray Code: Generating Gray Codes relies heavily on understanding how bit patterns change between adjacent indices, often using XOR and shifts similar to the logic found here.

While no other problems in the current curriculum map identically to this subpattern, mastering the i vs i >> 1 relationship is foundational for advanced bit manipulation questions.

Reference Implementation

C++ Solution for LeetCode 338

1class Solution {
2public:
3    vector<int> countBits(int n) {
4        // Initialize vector of size n + 1 with 0s
5        vector<int> ans(n + 1, 0);
6        
7        // Iterate from 1 to n to fill the DP table
8        for (int i = 1; i <= n; ++i) {
9            // relation: ans[i] = ans[i / 2] + (i % 2)
10            // implemented using bitwise operators for efficiency
11            ans[i] = ans[i >> 1] + (i & 1);
12        }
13        
14        return ans;
15    }
16};

Java Solution for LeetCode 338

1class Solution {
2    public int[] countBits(int n) {
3        // Initialize result array of size n + 1
4        int[] ans = new int[n + 1];
5        
6        // ans[0] is implicitly 0, so we start from 1
7        for (int i = 1; i <= n; i++) {
8            // ans[i >> 1] retrieves the count for i / 2
9            // (i & 1) checks if the current number is odd
10            ans[i] = ans[i >> 1] + (i & 1);
11        }
12        
13        return ans;
14    }
15}

Python Solution for LeetCode 338

1class Solution:
2    def countBits(self, n: int) -> List[int]:
3        # Initialize DP array with 0 for the base case
4        ans = [0] * (n + 1)
5        
6        # Iterate from 1 to n
7        for i in range(1, n + 1):
8            # i >> 1 is equivalent to i // 2
9            # i & 1 is equivalent to i % 2
10            ans[i] = ans[i >> 1] + (i & 1)
11            
12        return ans