Counting Bits (LC 338)

Pattern: Dynamic Programming + Bit Trick
Difficulty: Easy
Key Concept: count[i] = count[i >> 1] + (i & 1) — the count for i is the count for half of i, plus whether the last bit is 1.

Problem Statement

Given an integer n, return an array ans of length n + 1 such that ans[i] is the number of 1 bits in the binary representation of i for every i in [0, n].

Input

n: int, 0 <= n <= 10^5

Output

int[] of length n + 1 — Hamming weight for each i from 0 to n

Example

n = 2 → [0, 1, 1]
n = 5 → [0, 1, 1, 2, 1, 2]

1. Algorithm & Pseudocode

Brute force

For each i from 0 to n, count bits by scanning all 32 positions (or while i > 0 with % 2 / division—slower constants).

ans = new array[n+1]
for i from 0 to n:
    ans[i] = popcountBrute(i)   // loop bits or repeated mod 2
return ans

Optimal (DP)

Reuse answers already computed for smaller numbers:

ans[0] = 0
for i from 1 to n:
    ans[i] = ans[i >> 1] + (i & 1)
return ans

i >> 1 drops the last bit; i & 1 is that last bit.

Alternative trick: ans[i] = ans[i & (i-1)] + 1 (one fewer set bit than i).

2. Step-by-Step Analysis (Beginner-Friendly)

Why DP applies You need weights for all numbers up to n. Once ans[k] is known for k < i, you want a formula linking ans[i] to some ans[smaller].
Why i >> 1 Right shift by one removes the least significant bit. The popcount of i equals popcount of i/2 plus the removed bit (0 or 1).
Why not re-count from scratch Re-counting each i costs O(log i) or O(32) per i → about O(n log n) or O(32n). The recurrence is O(1) per i → O(n) total.
Base case ans[0] = 0 Zero has no 1 bits.

3. The Dry Run

Sample: n = 5. Optimal DP: ans[i] = ans[i >> 1] + (i & 1).

`i`	binary	`i >> 1`	`ans[i>>1]`	`i & 1`	`ans[i]`
0	000	—	—	—	0 (base)
1	001	0	0	1	1
2	010	1	1	0	1
3	011	1	1	1	2
4	100	2	1	0	1
5	101	2	1	1	2

Result: [0, 1, 1, 2, 1, 2].

ASCII: split last bit

i = 13:  1 1 0 1
         ^^^^^ ^  --> i>>1 = 110, last bit = 1
ans[13] = ans[6] + 1

4. Java Solution

Brute Force

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i;
            int c = 0;
            while (x > 0) {
                c += (x & 1);
                x >>>= 1; // logical shift; safe for counting bits of i in [0,n]
            }
            ans[i] = c;
        }
        return ans;
    }
}

Time: O(n log n) — each i takes up to O(log i) bit tests.
Space: O(1) extra besides output array.

Optimal

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;
    }
}

Time: O(n) — one recurrence per i.
Space: O(1) extra besides output.

5. The “Java vs. Others” Edge

>>> vs >> When iterating while (x > 0) with right shift, >>> avoids sign-extension on negative x. Here i is non-negative, so >> on i is fine; using >>> in the brute loop is a habit for “bit walk” code.
Array length n + 1 Off-by-one is a classic bug; ans[0] must exist.
Python List comprehension with bin(i).count('1') is readable but O(n · bits) and slower; the DP recurrence is the “serious” answer.

6. Complexity Summary

Approach	Time	Space	Notes
Brute (per-value bit scan)	O(n log n)	O(1) extra	Simple nested loops.
Optimal DP	O(n)	O(1) extra	`ans[i] = ans[i>>1] + (i&1)`.
Variant `i & (i-1)`	O(n)	O(1) extra	`ans[i] = ans[i & (i-1)] + 1`.