The O(n) Club: Counting Bits: Why Loop When You Can Cheat?

The O(n) Club: Counting Bits: Why Loop When You Can Cheat?

⚡ TL;DR

Given n, return an array of the number of 1’s (set bits) in each integer’s binary form from 0 to n. Sure, you could brute force every bit for every number—if you hate your own efficiency:

// Brute force version (yikes!):
int[] countBits(int n) {
    int[] res = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0, x = i;
        while (x != 0) {
            count += x & 1;
            x >>= 1;
        }
        res[i] = count;
    }
    return res;
}

Or, you could flex with DP and bit hacks and get it done in O(n) like the legend you are:

// Dynamic Programming (real devs approach):
int[] countBits(int n) {
    int[] res = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

🧠 How Devs Usually Mess This Up

Popular rookie mistake: treat every number like totally new work. You write a double loop, count the bits from scratch, and smile as your runtime combusts (congrats, you found O(n * 32)). The other fan-favorite is getting tangled in the bit logic—’Wait, is right shift just divide by 2? Why am I adding i & 1 again?’ Welcome to bitwise therapy, please bring snacks.

🔍 What’s Actually Going On

Here’s the bitwise magic: for every number, its number of set bits = the bits in its “parent” (the number after right-shift) + 1 if its last bit is a 1. Think inheritance, but for bits. So res[i] = res[i / 2] + (i % 2); in code, that’s res[i] = res[i >> 1] + (i & 1). Quickly, efficiently, with a side of mathematical smugness.

If you want to look like a real bit ninja, there’s also the res[i] = res[i & (i-1)] + 1 trick—which drops the lowest set bit, showing off the ancestry line for bit count.

🛠️ PseudoCode

• Create an array res of size n+1.
• res[0] = 0 because zero isn’t fooling anyone.
• For i = 1 to n:
  • Right-shift i (i >> 1) to get the parent bit count.
  • Add (i & 1) to include the last bit if it’s a 1.
  • res[i] = res[i >> 1] + (i & 1)
• Return res and act like you’ve always coded this way.

💻 The Code

public int[] countBits(int n) {
    int[] res = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

// Want to drop bits like it’s hot? Try: for (int i = 1; i <= n; i++) { res[i] = res[i & (i - 1)] + 1; }

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Case: n = 0 is fine, thanks to your solid initialization. You remembered res[0], right?
• Space: O(n). Sorry, you have to store every result. Your RAM is safe from infinite arrays.
• Time: O(n). Not O(n * bits per int). If you see a while-loop per i, run.
• Don’t reach for Java built-ins like Integer.bitCount—use them only to impress grandmas, not interviewers.

🧠 Interviewer Brain-Tattoo

“Don’t count everything from zero: let your previous work do the heavy lifting. Binary numbers are just lazy overachievers reusing their parents’ answers one bit at a time.”