Counting Bits

Problem Description

Given an integer n, return an array ans of length n + 1 such that for each i (0 ≤ i ≤ n), ans[i] is the number of 1 bits in the binary representation of i.

Examples

Constraints

• 0 ≤ n ≤ 10⁵

Extending Bit Counts from Shipped Subproblems

The naive solution runs the “Number of 1 Bits” algorithm on each number from 0 to n. Counting bits for each number independently takes O(n * log n) time.

To optimize to O(n) time, we can use dynamic programming by reusing the bit counts of smaller numbers we have already computed.

Notice the relationship between a number i and i / 2 (which is i >> 1 shifted right by one bit):

• Shifting i right by one bit removes the least significant bit.
• The number of set bits in i is equal to the number of set bits in i >> 1, plus 1 if i is odd (meaning its last bit was 1).
• This yields the O(1) state transition: dp[i] = dp[i >> 1] + (i & 1).

By iterating from 1 to n, we build the entire output array in linear time.

Solution 1: Dynamic Programming (LSR Offset)

Populate the output array using the recurrence relation: ans[i] = ans[i >> 1] + (i & 1).

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        ans[0] = 0; // base case

        for (int i = 1; i <= n; i++) {
            // state transition: shift right + check least significant bit
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        ans[0] = 0  # base case

        for i in range(1, n + 1):
            # state transition: shift right + check least significant bit
            ans[i] = ans[i >> 1] + (i & 1)

        return ans

#include <vector>

class Solution {
public:
    std::vector<int> countBits(int n) {
        std::vector<int> ans(n + 1, 0);
        ans[0] = 0; // base case

        for (int i = 1; i <= n; i++) {
            // state transition: shift right + check least significant bit
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We populate each array slot in constant time.
• Space Complexity: O(1) auxiliary space (the output array of size n + 1 does not count towards complexity by convention).

Where it breaks: Nothing breaks. It handles all numbers within the range correctly and uses the minimum possible memory.

Common Mistakes

• Forgetting parentheses around bitwise operator checks. Bitwise operator precedence is lower than addition in C++ and Java. Writing ans[i >> 1] + i & 1 evaluates as (ans[i >> 1] + i) & 1, which is incorrect. Use parentheses: (i & 1).
• Calculating values out of order. Because the state transition requires ans[i >> 1], you must iterate forward from 1 to n so that the subproblem value is already computed when needed.
• Using a full division i / 2 instead of bitwise right shift i >> 1. While they are mathematically identical, using bitwise shift operators is faster and cleaner for bit manipulation problems.

Frequently Asked Questions

Can we solve this using the most significant bit offset? Yes. You can use the most significant bit (MSB) offset: ans[i] = 1 + ans[i - offset], where offset is the largest power of 2 less than or equal to i (which resets when i reaches a new power of 2, like 2, 4, 8, 16). This is also O(n) but requires tracking the offset value.

What is the benefit of the right-shift DP method over binary representation string counts? Using bin(i).count('1') in Python translates the number to a string and scans it, which is O(log n) per number, making the total run time O(n log n). The DP method runs in pure O(n) without string conversions.

What does this problem test in interviews? It tests your ability to apply dynamic programming state-sharing principles to bit manipulation operations.

← All Problems