Problem Link

LeetCode Version

Problem Statement

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's in the binary representation of i.

Example :

//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

Problem Understanding:

I’m not going to lie to you — yes, this LeetCode problem is labeled as “easy,” but I didn’t understand it at first. It felt like I was reading in French, and my brain just refused to process it. This is kind of what happens to a computer when it tries to read plain English — it doesn't get it. Computers think in binary: just 0s and 1s. Every number we use can be represented as a sequence of these two digits, and that’s what we call its binary representation. A 1 represents a bit turned on and A 0 represents a bit turned off. Amazing, right? In its simplest form, this is what computers are doing 24/7 — flipping switches on and off.

So, for example:

n = 5 → binary is 101 → this has two 1s and one 0

What is the problem really asking?

Given a number n, create an array that for every number from 0 to n:
- Stores how many 1s are in the binary form of that number.

So if n=5, your array would look like:

  Index:    0 1 2 3 4 5
  Number:   0 1 2 3 4 5
  Binary:  0 1 10 11 100 101
  Count:   0 1 1 2 1 2
  Result: [0,1,1,2,1,2]

This is the heart of the problem — and once you get that, you're ready to start thinking like a computer.

The Brute Force

So now that I finally understood what the question was asking (after two cups of coffee and a mini identity crisis), I had a very human thought:

“What if I just converted every number to binary, then counted how many 1s are in it?”

Sounds human enough, right? But then the question became: how do I convert a number to binary? Plot twist: JavaScript makes it weirdly easy with .toString(2). This handy little trick converts a number to its binary representation as a string. And honestly, strings are easier to visualize and loop through — especially if you're not used to thinking in bits.

So now our logic is simple:

Convert the number to a binary string.
Loop through the string.
Count every time you see a '1'.
Push that count into the result array.

var countBits = function(n) {
    let result = [];

    for (let i = 0; i <= n; i++) {
        let binary = i.toString(2); // Convert number to binary
        let count = 0;

        for (let char of binary) {
            if (char === '1') count++; // Count the 1s manually
        }

        result.push(count);
    }

    return result;
};

Time Complexity: O(n * k), where k is the average number of bits in the binary representation (≈ log₂n).
Space Complexity: O(n) for the result array (plus some temporary space for each binary string).
Why not to Use: While this approach works and is perfect for understanding the basics, it's not the most efficient:

You're converting every number to a string, which is more expensive than needed.
Then you're looping over that string, which adds an extra step.
You're not really using the fact that binary is just… math. The computer already knows how to do it better.

But hey — if you’re a beginner or just trying to get a working solution first, this is a perfectly valid and very readable approach. The important thing is that now you understand what the question is doing and what binary actually means.

Ready to go deeper and think like the computer itself? On to the optimized version..

2. Dynamic Programming with Bitwise

At some point, you realize… maybe we don’t need to convert to binary strings at all. What if we could think in bits, just like the computer? This is the beauty of coding , keep wondering keep asking question , keep thinking That’s when you learn about this gem of an insight:

The number of 1s in a number i is equal to:
countBits[i >> 1] + (i & 1)

Translation for humans, aka(moi et toi) :

i >> 1 = “shift bits to the right” = divide i by 2 and drop the decimal
i & 1 = is the last bit of i a 1? (returns 1 or 0)

So we build on already computed results to avoid doing any counting from scratch.

var countBits = function(n) {
    let result = [0]; // Base case: 0 has zero 1s

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

    return result;
};

Time Complexity: O(n) – Bit shifting is super fast. No strings. No nested loops. Just binary wizardry.
Space Complexity: O(n)
Why Use: This solution feels like telling the computer, "Hey buddy, you already figured this out before. Use your memory."

3. Optimal Approach: Iterative (Bottom-Up Dynamic Programming)

Now, for the math nerds and curious minds, there’s a third approach. It's not faster in complexity, but it feels clever. It’s like understanding the problem from a bird’s-eye view.

Here’s the idea:

Between every power of two, the pattern of 1s repeats — just with one more 1 in front.

Example:

0 → 000
1 → 001
2 → 010
3 → 011
Then comes 4 → 100 ← next power of two!

So for numbers between 4 and 7 (i.e. 5, 6, 7You’re basically copying the earlier pattern and slapping a 1 in front.

This leads to the pattern:

countBits[i] = 1 + countBits[i - offset]

Where offset is the largest power of 2 less than or equal to i.

The Code:

var countBits = function(n) {
    let result = [0];
    let offset = 1;

    for (let i = 1; i <= n; i++) {
        if (offset * 2 === i) offset = i;
        result[i] = 1 + result[i - offset];
    }

    return result;
};

Why this is cool:

You're not just computing; you’re recognizing patterns.
You track when a new power of two is reached, and use that to build the next block of numbers.

If the intermediate solution is like giving the computer a map, this one is like teaching it to spot patterns in the terrain.

Final Thoughts

So what did we actually do here? We took a problem that looked deceptively simple — “just count the 1s in a binary number” — and ended up on a journey through human logic, bitwise shortcuts, and even pattern recognition in powers of two.

Let’s recap the three mindsets we took:

🐣 Level 1: The Human Approach (Brute Force)

“I don't speak binary. Let me just convert this to a string and count some characters.”

✅ Easy to understand
🧠 Requires zero bitwise knowledge
🐢 Slow for large inputs

It’s like solving a math problem with your fingers and toes — it works, but it’s not scalable.

🧠 Level 2: The Computer’s Approach (Bitwise DP)

“I’ve seen this before. Let me just reuse my old answers with a bitwise twist.”

⚡ Fast and efficient (O(n))
💡 Uses shifting (>>) and masking (& 1)
📚 Teaches you how computers actually think

This is where you graduate from “coding with vibes” to “coding with precision.”

🧙 Level 3: The Mathematician’s Pattern Recognition

“Every time we reach a new power of two, the 1s reset and repeat... but smarter.”

🧬 Elegant and insightful
💥 Makes use of structure and patterns
✨ Bonus points for seeing beneath the surface

It’s like looking at numbers and saying, “Wait, there’s a system here.”

The Big Lesson?

Binary might look like a scary wall of 0s and 1s, but it's really just another way to count — and once you crack the code, it becomes a superpower.

So whether you’re looping through strings, shifting bits like a hacker, or spotting powers of two like a wizard, you’re leveling up.

Keep building. Keep exploring. And remember: even computers had to learn binary once.

LeetCode: Counting Bits