Counting Bits — Linear-Time Popcount Using a One-Line Bit DP

Problem Statement#

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

Constraints:

• 0 <= n <= 10^5
• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass? Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Example 1:

Input:  n = 2
Output: [0, 1, 1]
Explanation: 0 -> 0, 1 -> 1, 2 -> 10

Example 2:

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

Example 3:

Input:  n = 0
Output: [0]

Why This Problem Matters#

Counting Bits looks like a trivial popcount loop, but the LeetCode follow-up — "do it in O(n) without built-ins" — promotes it to a real interview problem. The elegant solution combines dynamic programming with bit manipulation, two pillars of interview prep, into a single-line recurrence. Recruiters at Amazon, Apple, and Meta use this question to test whether candidates can recognize bit-shifting structure inside a DP problem.

The key insight transfers far beyond this one problem. Once you see that i shares popcount structure with smaller numbers (specifically i >> 1), you have a template for many bitwise DP problems including subset-sum DP, masked traveling salesman, and bitmask DP for assignment problems. It also reinforces the relationship between binary representations and recursion — every integer is its right-shifted half plus a single trailing bit.

The Core Insight#

For any positive integer i, observe its binary structure:

• i = (i >> 1) shifted left by one position, plus the lowest bit (i & 1).

Therefore:

popcount(i) = popcount(i >> 1) + (i & 1)

The right-shift removes the lowest bit; the lowest bit itself is either 0 or 1 and is exactly i & 1. Combined, we know the popcount of i from the popcount of a smaller, already-computed number.

This yields the DP recurrence:

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

Since each dp[i] requires only one previously computed value, we fill the table in O(n) total time using O(n) space (the output array itself).

Alternative recurrence using Brian Kernighan:

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

Because i & (i - 1) clears the lowest set bit, dp[i] is one more than the popcount of that smaller number. Both recurrences are O(n); the right-shift form is more common in interviews.

Visual Dry Run#

Compute dp[0..7]:

Result: [0, 1, 1, 2, 1, 2, 2, 3]. Each entry uses one earlier entry — pure linear DP.

Solution (Optimal)#

Python#

class Solution:
    def countBits(self, n: int) -> list[int]:
        # dp[i] = popcount of integer i
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            # right-shift drops the lowest bit; (i & 1) recovers it
            dp[i] = dp[i >> 1] + (i & 1)
        return dp

JavaScript#

var countBits = function(n) {
    // dp[i] = number of set bits in i
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        // right-shift removes the lowest bit; restore it via (i & 1)
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
};

Complexity: Time O(n), Space O(n) for the output array (no auxiliary space beyond it).

Common Mistakes#

1. Using a nested loop O(n log n) when O(n) is asked. Calling popcount(i) for every i independently gives O(n log n) total work. The DP recurrence reuses prior results to achieve O(n).

2. Mixing up dp[i >> 1] with dp[i / 2] for negative inputs. For non-negative i they coincide, but right-shift on negative numbers in signed languages performs arithmetic shift, which is not the same as integer division toward zero. The constraints guarantee n >= 0 so this is moot here, but worth understanding.

3. Indexing past the array end. Off-by-one: the output has length n + 1 because we include both 0 and n. New candidates sometimes allocate n cells.

4. Reaching for built-ins after the interviewer disallowed them. LeetCode explicitly bans __builtin_popcount. Using bin(i).count('1') defeats the educational purpose; demonstrate the DP.

5. Forgetting dp[0] = 0 is implicit but required. Initializing the array with zeros handles this naturally; manual loops sometimes start at i = 0 and re-derive zero unnecessarily.

Interview Tips#

• Open by saying "I notice that every integer is its right-shifted half plus a trailing bit." This frames the recurrence cleanly.
• Mention the alternative dp[i] = dp[i & (i - 1)] + 1 formulation — it shows you know Brian Kernighan and can pick between equivalent recurrences.
• For senior interviews, discuss whether the DP can be done in-place (yes — the output is the only memory) and whether SIMD popcount would beat the DP for very small n (yes, due to vectorization).
• If the interviewer relaxes the linear constraint, mention the lookup table approach: precompute popcount for all 8-bit values, then sum byte-wise. O(n) time, near-zero branching.

Follow-up Questions#

Q: Why does dp[i] = dp[i >> 1] + (i & 1) work? Because shifting right by one bit removes the lowest bit, and adding (i & 1) reinstates whether that bit was set. The popcount of i equals the popcount of its half plus the parity of i.

Q: Could we compute the answer in O(1) extra space (excluding output)? Yes — the output array is the only storage we use. The DP is in-place over the output.

Q: How does this relate to Number of 1 Bits (LC 191)? LC 191 computes popcount for one number; LC 338 computes it for all numbers up to n. The DP exploits overlapping subproblems that LC 191 cannot.

Q: What if n is up to 10^9? The DP would need 4 GB of memory. You'd compute popcount per query using Brian Kernighan's loop in O(log n) per call, or use 8-bit / 16-bit lookup tables for batched popcounts.

Key Takeaways#

• The recurrence dp[i] = dp[i >> 1] + (i & 1) solves Counting Bits in linear time using the binary structure of integers.
• Equivalent formulation dp[i] = dp[i & (i - 1)] + 1 uses Brian Kernighan's lowest-bit-clearing identity.
• Each value reuses one prior value, achieving O(n) time and O(1) extra memory beyond the output.
• This pattern — right-shift recurrences — generalizes to many bitmask DPs and digit-DP problems.
• Avoid O(n log n) per-element popcount when a linear DP is requested; recognize the bit-level overlap.
• Pair this knowledge with hardware popcount instructions for production code while demonstrating the algorithmic insight in interviews.