338. Counting Bits

Counting Bits is the problem that makes the “reuse an answer you already computed” habit click on a bit-level task. The naive version counts each number from scratch; the good version notices that i shares almost all its bits with a number it already solved. It sits in the bit manipulation pattern, where reading a number bit by bit turns an O(word-size) loop into O(1) work.

The problem

Given a non-negative integer n, return an array of length n + 1 where entry i holds the number of 1 bits in the binary form of i. (Full statement on LeetCode.)

For n = 5 the answer is [0, 1, 1, 2, 1, 2] — because 4 is 100 (one set bit) and 5 is 101 (two).

Intuition: strip the last bit and you’ve seen the rest before

The baseline is easy: for each number, count its bits. That’s a call to Integer.bitCount (or a manual loop) per value — correct, but you redo work across numbers that share structure. The follow-up on this problem asks for a single linear pass, and the trick is to build each answer from a smaller one you already have.

Here’s the relationship. Take any i and shift it right by one bit: i >> 1 drops the lowest bit and keeps everything above it. So i has exactly the set bits of i >> 1, plus one more if the bit you dropped was a 1. That dropped bit is just i & 1 — 1 when i is odd, 0 when it’s even:

$\text{bits}(i) = \text{bits}(i \gg 1) + (i \,\&\, 1)$

Because i >> 1 < i for every i >= 1, that smaller answer is already sitting in the array by the time you reach i. One lookup, one add, done — no inner loop over the bits at all. The base case is free: bits(0) = 0.

If you’d rather remove the lowest set bit than the lowest bit, i & (i - 1) clears it, giving bits(i) = bits(i & (i - 1)) + 1. Same linear idea, different subproblem — both are fair game.

Solution

The shift recurrence turns into a three-line loop. dp[0] is already 0 from the array default, so start at 1:

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];       // dp[0] = 0 by default
        for (int i = 1; i <= n; i++) {
            // i has the bits of i>>1, plus 1 if i's lowest bit is set
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}

For contrast, the baseline the follow-up wants you to beat leans on a built-in and recounts every value from zero:

class Solution {
    public int[] countBitsBaseline(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ans[i] = Integer.bitCount(i);  // ~O(1) here, but recomputed each time
        }
        return ans;
    }
}

Both return the right array. The first is what an interviewer is fishing for, because it shows you found the overlap between subproblems instead of reaching for a library call.

Complexity

Approach	Time	Space
DP with bit shift	$O(n)$	$O(n)$
Baseline with Integer.bitCount	$O(n)$	$O(n)$
Manual per-bit count loop	$O(n \cdot k)$	$O(n)$

Be honest about the baseline: Integer.bitCount(int) does a fixed amount of work on a 32-bit value, so the shown baseline is $O(n)$ too — the DP matches it asymptotically rather than beating it. The $O(n \cdot k)$ (with $k$ the word size) only appears if you hand-roll a bit-by-bit count for each number. The real payoff of the DP isn’t a lower big-O; it’s that it finds the shared substructure and drops the library call. The output array is $O(n)$ in every version — you’re asked to return it.

In an interview

Say the recurrence in words before writing code: “the count for i is the count for i shifted right by one, plus one if i is odd.” That single sentence proves you spotted the shared substructure, which is the whole point of the exercise. The trap is defaulting to Integer.bitCount in a loop and calling it done — it’s actually $O(n)$ and passes, but it leans on a library call instead of the subproblem insight the problem is testing, and a sharp interviewer will push you for the DP anyway.

The bit-reading half of this — pulling out one bit at a time — is the same move behind Number of 1 Bits, and the “drop a bit and recurse” framing shows up again in Reverse Bits. The full family lives in the bit manipulation pattern.

References

• LeetCode 338 — Counting Bits