Counting Bits

EasyBit Manipulation · DP🧩 Bit Manipulation LeetCode #338 ↗Updated Oct 30, 2026

Problem

Given a non-negative integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every 0 ≤ i ≤ n.

Inputn = 2Output[0,1,1]

Inputn = 5Output[0,1,1,2,1,2]

0 ≤ n ≤ 10⁵ · Follow-up: O(n) in a single pass, without built-ins like Integer.bitCount.

Try it yourself

Java

class Solution {
    public int[] countBits(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Every number is a smaller number plus one bit: i equals i >> 1 with its last bit (i & 1) appended. So ans[i] = ans[i >> 1] + (i & 1) reuses an answer already computed.

PatternBit Manipulation

Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.

Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.

Open the Bit Manipulation guide →

Approaches

Brute ForceCount Each Number Bit by Bit

Time O(n log n)Space O(1) extra

For each i, peel off bits with % 2 and / 2 until it reaches 0. A number has about log₂i bits, so the total work is O(n log n). (The output array itself is O(n) and not counted.)

Java

public int[] countBits(int n) {
    int[] res = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0, num = i;
        while (num > 0) {
            count += num % 2; // lowest bit
            num /= 2;         // drop it
        }
        res[i] = count;
    }
    return res;
}

Obvious and correct, but recomputes overlapping work for every number.

BetterDP on Highest Power of Two

Time O(n)Space O(1) extra

If 2^m ≤ i < 2^m+1, then i = 2^m + k with k < 2^m, so i has one more set bit than k. Track the current power x and use res[i] = res[i - x] + 1.

Java

public int[] countBits(int n) {
    int[] res = new int[n + 1];
    int pow = 1, x = 1; // next power of two, current power of two
    for (int i = 1; i <= n; i++) {
        if (i == pow) {
            x = pow;
            pow *= 2;
        }
        res[i] = res[i - x] + 1; // strip the top bit
    }
    return res;
}

Linear, but needs extra bookkeeping to track the current power of two.

OptimalDP on Last Bit (i >> 1)

Time O(n)Space O(1) extra

Shifting right drops the lowest bit, so i >> 1 has the same set bits as i minus that last bit. Since i >> 1 < i, its answer is ready: res[i] = res[i >> 1] + (i & 1).

Java

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); // half's bits + last bit
    }
    return res;
}

Dry runn = 5

i ih i >> 1 changed

i=1
0
h
1
i
·

·

·

·

res[0]+1 = 1
i=2
0

1
h
1
i
·

·

·

res[1]+0 = 1
i=3
0

1
h
1

2
i
·

·

res[1]+1 = 2
i=4
0

1

1
h
2

1
i
·

res[2]+0 = 1
i=5
0

1

1
h
2

1

2
i
res[2]+1 = 2 ✔

One pass, O(1) per number, no state — the cleanest O(n) answer.

Pro tip

Equivalent recurrence: res[i] = res[i & (i - 1)] + 1 (i & (i-1) clears the lowest set bit).

At a glance

Level	Approach	Time	Space
Brute Force	Count Each Number Bit by Bit	`O(n log n)`	`O(1) extra`
Better	DP on Highest Power of Two	`O(n)`	`O(1) extra`
Optimal	DP on Last Bit (i >> 1)	`O(n)`	`O(1) extra`

Common pitfalls

Allocating n instead of n + 1 slots — misses ans[n].
Operator precedence: res[i >> 1] + i & 1 parses as (res[..] + i) & 1.
Starting the DP loop at 0 without the base case res[0] = 0 in mind.

Interview tips

Start with per-number counting, then spot that i and i/2 share bits.
Name it as DP: subproblem i >> 1 is always solved earlier.
Mention i & (i-1) (Kernighan) — it reappears in Number of 1 Bits and Power of Two.

Pattern

Bit DP → when a value's answer for i follows from a smaller related value (i>>1, i&(i-1)).

My notes saved in this browser