LeetCode 338: Counting Bits Explained | Java | Dynamic Programming + Bit Manipulation | Blind 75

Have you ever wondered how your computer can quickly tell the number of 1s in every number from 0 to n without recalculating everything from scratch?

This problem looks like a simple extension of Number of 1 Bits, but there’s a catch — you need to compute the answer for every number from 0 to n.

Companies like Google, Microsoft, Amazon, Meta, and Apple love this problem because it tests whether you can recognize patterns and optimize repeated work using Dynamic Programming.

In this article, we’ll build the intuition behind the Counting Bits problem from the Blind 75 list.

What You’ll Learn

By the end of this article you’ll know

✅ Why recalculating bits repeatedly is inefficient

✅ The pattern hidden inside binary numbers

✅ Two approaches to solve the problem

✅ Dynamic Programming intuition

✅ Dry Run

✅ Time Complexity

✅ Interview Tips

✅ Related Problems

Problem Statement

Given an integer n, return an array ans of length n + 1 such that

ans[i] is the number of 1's in the binary representation of i.

Example

Input n = 5

Output

[0,1,1,2,1,2]

Real World Analogy

Imagine a data center with servers numbered from 0 to n.

Each server has a 32-light status panel, where:

• ON lights (1) represent active services.
• OFF lights (0) represent inactive services.

Your task is to create a report showing how many services are active on every server, from server 0 to server n.

You are not interested in just one server — you need the count for all of them.

This is exactly what the problem asks: for every number from 0 to n, count how many bits are turned ON.

Approach 1: Calculate Each Number Independently

The most straightforward solution is to compute the number of set bits for every integer individually.

For every number from 0 to n, we repeatedly inspect each bit and count the number of 1s.

This works, but we’re doing the same work again and again.

For example, while calculating the answer for 7, we inspect many of the same bits that were already processed for 6, 5, and 4.

Algorithm

1. Create an answer array.

2. For every number from 0 to n:

Count its set bits using bit manipulation.

Store the result.

3.Return the answer array.

Java Code

class Solution {

    public int[] countBits(int n) {

        int[] ans = new int[n + 1];

        for (int i = 0; i <= n; i++) {

            int num = i;
            int count = 0;

            while (num != 0) {
                count += (num & 1);
                num >>>= 1;
            }

            ans[i] = count;
        }

        return ans;
    }
}

⏱️ Complexity Analysis

Time Complexity: O(n × 32)

Each number may require checking all 32 bits.

Overall complexity is linear with a constant factor.

Space Complexity: O(1)

Ignoring the output array.

Can We Do Better?

Yes.

Notice something interesting.

Suppose we already know:

2 = 10 → 1 bit
3 = 11 → 2 bits
4 = 100 → 1 bit

Can we compute the answer for a new number using a previously computed answer?

Absolutely.

Instead of counting every bit again, we reuse answers we’ve already calculated.

This leads us to Dynamic Programming.

Approach 2: Dynamic Programming (Optimal)

Observe the binary representation carefully.

0 = 000

1 = 001

2 = 010

3 = 011

4 = 100

5 = 101

6 = 110

7 = 111

Now divide every number into two parts.

Remaining Bits + Last Bit
For Example , 
6 = 110

Remaining bits = 11 (3)

Last bit = 0

The number of set bits becomes

bits(6) = bits(3) + 0

This gives us the recurrence:

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

This is the key observation.

• i >> 1 removes the last bit.
• i & 1 tells whether the removed bit was 1.

Since we’ve already computed bits(i >> 1), we can compute bits(i) in constant time.

Algorithm

1.Create an array of size n + 1.

2.Start from 1.

3.For every number: ans[i] = ans[i >> 1] + (i & 1)

4 .Return the answer array.

Java Code

class Solution {

    public int[] countBits(int n) {

        int[] ans = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }

        return ans;
    }
}

⏱️ Complexity Analysis

Time Complexity: O(n)

Each number is processed exactly once.

Each computation takes constant time.

Space Complexity: O(n)

The answer array stores one value for every number.

Why Is This Better?

Compared to calculating each number independently:

• Every answer is computed only once.
• Previously computed results are reused.
• Each number requires only one simple formula.
• No repeated bit counting.

For example,

n = 1,000,000

The brute-force approach repeatedly examines bits for every number.

The Dynamic Programming approach performs only one constant-time computation per number, making it significantly faster.

Key Takeaway

Whenever you need answers for every number from 0 to n, avoid solving each problem independently.

Look for a relationship between consecutive numbers.

The recurrence

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

is one of the most elegant Dynamic Programming formulas involving bit manipulation and is a common interview pattern.

Conclusion

Although Counting Bits looks like an extension of Number of 1 Bits, the real challenge is avoiding repeated computation.

We explored two approaches:

• Calculate each number independently to build intuition.
• Dynamic Programming using the recurrence ans[i] = ans[i >> 1] + (i & 1) for the optimal solution.

Understanding this pattern will make many Dynamic Programming and Bit Manipulation problems much easier to solve.

This article is part of my Blind 75 in Java series.

➡️ Next: Reverse Bits (LeetCode 190)

If you found this article helpful, consider following me for more beginner-friendly Java interview solutions.

Happy coding! 🚀