Counting Bits

Problem Statement

Given a non-negative integer n, build an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every i from 0 through n.

The challenge is to do it in a single linear pass, without counting the bits of each number from scratch.

Examples

Example 1:

Input: n = 3
Output: [0,1,1,2]
Explanation: 0 = 0, 1 = 1, 2 = 10, 3 = 11.

Example 2:

Input: n = 6
Output: [0,1,1,2,1,2,2]
Explanation: 4 = 100, 5 = 101, 6 = 110.

Example 3:

Input: n = 0
Output: [0]
Explanation: The array has one entry, the bit count of 0.

Constraints

• 0 <= n <= 10^5

Approach 1: Count Each Number Separately

Algorithm

Treat it as n + 1 independent Number of 1 Bits problems. For each i, repeatedly clear its lowest set bit with x & (x - 1) and count how many steps it takes to reach zero.

1. Create ans of length n + 1.
2. For each i from 0 to n:
   • Copy x = i and set count = 0.
   • While x != 0: x &= x - 1 and increment count.
   • Store ans[i] = count.
3. Return ans.

Implementation

Python:

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(n + 1):
            x, count = i, 0
            while x:
                x &= x - 1   # clear the lowest set bit
                count += 1
            ans[i] = count
        return ans

Java:

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i, count = 0;
            while (x != 0) {
                x &= x - 1;  // clear the lowest set bit
                count++;
            }
            ans[i] = count;
        }
        return ans;
    }
}

Go:

func countBits(n int) []int {
    ans := make([]int, n+1)
    for i := 0; i <= n; i++ {
        x, count := i, 0
        for x != 0 {
            x &= x - 1 // clear the lowest set bit
            count++
        }
        ans[i] = count
    }
    return ans
}

JavaScript:

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    const ans = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        let x = i, count = 0;
        while (x !== 0) {
            x &= x - 1; // clear the lowest set bit
            count++;
        }
        ans[i] = count;
    }
    return ans;
};

C#:

public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i, count = 0;
            while (x != 0) {
                x &= x - 1;  // clear the lowest set bit
                count++;
            }
            ans[i] = count;
        }
        return ans;
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for (int i = 0; i <= n; i++) {
            int x = i, count = 0;
            while (x != 0) {
                x &= x - 1;  // clear the lowest set bit
                count++;
            }
            ans[i] = count;
        }
        return ans;
    }
};

Complexity Analysis

• Time: O(n log n). Each number i has at most about log2(n) + 1 set bits, and the inner loop runs once per set bit.
• Space: O(1) extra beyond the output array of size n + 1.

Approach 2: DP on the Right Shift (Optimal)

Algorithm

Shifting i right by one drops its lowest bit and keeps every other bit. So the bit count of i is the bit count of i >> 1 plus whatever that dropped bit was:

ans[i] = ans[i >> 1] + (i & 1)

For example, 13 = 1101 and 13 » 1 = 6 = 110. ans[6] = 2, and the dropped bit is 1, so ans[13] = 3.

Because i >> 1 < i for every i >= 1, the value we need has always been computed already when we fill the array left to right.

1. Create ans of length n + 1 with ans[0] = 0.
2. For i from 1 to n: ans[i] = ans[i >> 1] + (i & 1).
3. Return ans.

Implementation

Python:

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            # i >> 1 has the same bits as i, minus the lowest one
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

Java:

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // i >> 1 has the same bits as i, minus the lowest one
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

Go:

func countBits(n int) []int {
    ans := make([]int, n+1)
    for i := 1; i <= n; i++ {
        // i >> 1 has the same bits as i, minus the lowest one
        ans[i] = ans[i>>1] + (i & 1)
    }
    return ans
}

JavaScript:

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    const ans = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        // i >> 1 has the same bits as i, minus the lowest one
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
};

C#:

public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // i >> 1 has the same bits as i, minus the lowest one
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            // i >> 1 has the same bits as i, minus the lowest one
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
};

Complexity Analysis

• Time: O(n). One constant-time step per number.
• Space: O(1) extra beyond the output array of size n + 1.

Key Insights

• Every number is a smaller number plus one bit. i >> 1 is always smaller than i, so a left-to-right fill can reuse its answer.
• There are several equivalent recurrences. ans[i] = ans[i & (i - 1)] + 1 (remove the lowest set bit) and ans[i] = ans[i - highestPowerOfTwo] + 1 (remove the highest set bit) are also O(n). Pick the one you can explain clearly.
• The output array is the DP table. No extra memory is needed beyond what the problem asks you to return.

Edge Cases

• n = 0: return [0]. The DP loop does not execute.
• n = 1: return [0, 1].
• Powers of two always have count 1, and 2^k - 1 has count k; these are good values to spot-check.
• n = 10^5: Approach 2 runs 100,000 constant steps; no overflow is possible since counts never exceed 17.

Common Mistakes

• Allocating n slots instead of n + 1. The range is inclusive of n.
• Operator precedence with &. In Python, Java, C#, C++ and JavaScript, ans[i >> 1] + i & 1 parses as (ans[i >> 1] + i) & 1. Wrap the bit test in parentheses: (i & 1). (Go is the exception: there & binds tighter than +, but the parentheses do no harm.)
• Starting the DP loop at 0 with the i & (i - 1) recurrence: it would compute ans[0] = ans[0 & -1] + 1 = 1, which is wrong. Start at 1 and leave ans[0] = 0.
• Calling a built-in popcount per number and calling it optimal. It is fast in practice, but the interviewer is usually looking for the DP relationship.

Interview Tips

• State the O(n log n) solution first, since it is simple and correct, then ask yourself what earlier answer each new number can reuse.
• Write out 0 to 8 in binary next to their counts; the pattern ans[2i] = ans[i] and ans[2i + 1] = ans[i] + 1 jumps out, which is exactly the right-shift recurrence.
• Mention the alternative i & (i - 1) recurrence to show you understand the general idea, not just one formula.

Follow-up Questions

• Can you do it without any built-in function? Yes, Approach 2 uses only a shift, an AND and an addition.
• What if you only need the total number of set bits from 0 to n? You can compute it per bit position in O(log n): for bit k, full blocks of length 2^(k+1) each contribute 2^k ones, plus a partial block.
• How does this relate to a single number’s count? Approach 1 is just the single-number solution in a loop; the DP shares work across numbers.

Related Problems

• Number of 1 Bits
• Power of Two
• Reverse Bits
• Climbing Stairs
• Sum of Two Integers