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:

text
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.

Core Insight for Counting Bits

The key intuition for the LeetCode 338 Solution lies in observing how the binary representation changes as numbers increase. Specifically, consider the relationship between a number $x$ and $x / 2$ (integer division).

In binary, performing integer division by 2 is equivalent to a right shift operation (>> 1).

• If we have a number $x = (1101_2)$, which is 13.
• Right shifting it gives $x >> 1 = (110_2)$, which is 6.

Notice that $x$ contains all the set bits of $x >> 1$, plus potentially one more bit at the Least Significant Bit (LSB) position.

• If $x$ is even, the LSB is 0. The number of set bits in $x$ is exactly the same as in $x/2$.
• If $x$ is odd, the LSB is 1. The number of set bits in $x$ is the number of set bits in $x/2$ plus 1.

This allows us to formulate a recurrence relation (transition equation) suitable for Dynamic Programming: $DP[i] = DP[i >> 1] + (i \& 1)$

Here, i >> 1 looks up the result for a smaller number that has already been computed, and i & 1 checks if the current number is odd (adding 1 if true, 0 if false).

Visual Description: Imagine filling the array from left to right. To find the value for index 14 (1110), you look at index 7 (111). Since 14 is 7 shifted left with a 0 appended, they have the same bit count. To find the value for index 15 (1111), you look at index 7 (111) and add 1 because 15 is 7 shifted left with a 1 appended. The algorithm builds the solution based on this "prefix" property of binary numbers.

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.

Reference Implementation

C++ Solution for LeetCode 338

cpp
class Solution {
public:
    vector<int> countBits(int n) {
        // Initialize vector of size n + 1 with 0s
        vector<int> ans(n + 1, 0);
        
        // Iterate from 1 to n to fill the DP table
        for (int i = 1; i <= n; ++i) {
            // relation: ans[i] = ans[i / 2] + (i % 2)
            // implemented using bitwise operators for efficiency
            ans[i] = ans[i >> 1] + (i & 1);
        }
        
        return ans;
    }
};

Java Solution for LeetCode 338

java
class Solution {
    public int[] countBits(int n) {
        // Initialize result array of size n + 1
        int[] ans = new int[n + 1];
        
        // ans[0] is implicitly 0, so we start from 1
        for (int i = 1; i <= n; i++) {
            // ans[i >> 1] retrieves the count for i / 2
            // (i & 1) checks if the current number is odd
            ans[i] = ans[i >> 1] + (i & 1);
        }
        
        return ans;
    }
}

Python Solution for LeetCode 338

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

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.