easy Counting Bits

Counting Bits

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of set bits in i, for every i from 0 to n. For n = 5 the answer is [0, 1, 1, 2, 1, 2].

The single-number version (Number of 1 Bits) is a warm-up. What makes this problem worth studying is that it is secretly a dynamic-programming problem on bits: the answer for i is one array lookup away from an answer you already computed. Spotting that recurrence is the whole point.

The naive baseline — popcount every number independently

Run a Hamming-weight count (e.g. Kernighan's x & (x-1) loop) once per value:

for (int i = 0; i <= n; i++) ans[i] = popcount(i);

Each popcount costs up to O(32) (or O(log i)) bit steps, so the total is O(n · 32). Correct, but it recomputes from scratch every time and throws away work it just did on smaller numbers.

The bit insight — reuse a smaller answer (two recurrences)

Recurrence A — drop the last bit: ans[i] = ans[i >> 1] + (i & 1). Right-shifting i by one deletes its lowest bit and keeps every other bit, just slid down one position. Shifting does not create or destroy the remaining 1s, so i >> 1 has exactly the set bits of i except the one we shifted out. That discarded bit was worth i & 1 (1 if i was odd, 0 if even). Hence popcount(i) = popcount(i >> 1) + (i & 1). And since i >> 1 < i for i > 0, that subproblem is already solved — a textbook overlapping subproblem.

Recurrence B — clear the last set bit: ans[i] = ans[i & (i - 1)] + 1. We proved on the previous page that i & (i - 1) removes exactly one set bit. So i & (i-1) has one fewer 1 than i, and it is strictly smaller than i, so it too is already computed. Add 1 for the bit we removed.

Either recurrence turns each entry into one comparison and one array read — O(1) per number, O(n) overall. This is dynamic programming: define the state (ans[i] = popcount of i), find a transition to a smaller solved state, fill bottom-up.

Traced example — n = 5, using ans[i] = ans[i>>1] + (i&1)

Result: [0, 1, 1, 2, 1, 2]. Cross-check by hand: 3 = 11 (2 bits), 4 = 100 (1 bit), 5 = 101 (2 bits). Every entry was one lookup plus a parity bit.

Java: DP on bits

public class Solution {
    // ans[i] = ans[i >> 1] + (i & 1)
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];   // ans[0] = 0 by default
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.toString(new Solution().countBits(5)));
        // [0, 1, 1, 2, 1, 2]
        System.out.println(java.util.Arrays.toString(new Solution().countBits(2)));
        // [0, 1, 1]
    }
}

Go: DP on bits

package main

import "fmt"

// ans[i] = ans[i>>1] + (i & 1)
func countBits(n int) []int {
	ans := make([]int, n+1) // ans[0] == 0 (zero value)
	for i := 1; i <= n; i++ {
		ans[i] = ans[i>>1] + (i & 1)
	}
	return ans
}

func main() {
	fmt.Println(countBits(5)) // [0 1 1 2 1 2]
	fmt.Println(countBits(2)) // [0 1 1]
}

Complexity

• Time: one pass over 1..n, doing O(1) work each — a shift, a mask, an add, and one array read — so O(n). The naive per-number popcount is O(n · 32); the DP removes the inner 32 factor by never rescanning bits.
• Space: O(n) for the output array; O(1) auxiliary beyond it. The output is required by the problem, so this is optimal.

Judgment layer — when the DP earns its place

• This problem specifically tests the recurrence. A correct-but-shallow answer calls a library popcount in a loop: ans[i] = Integer.bitCount(i). That is also O(n) wall-clock (hardware POPCNT is one instruction), so it is not wrong — but it dodges the exact skill the interviewer is probing, namely seeing that ans[i] reuses a smaller ans[·]. State the DP; mention the builtin as the pragmatic production choice.
• Recurrence A vs. B. ans[i>>1] + (i&1) is the one to reach for — it is symmetric, obviously correct, and does not depend on the earlier x & (x-1) lemma. ans[i&(i-1)] + 1 is a nice flex when you want to show you internalized the lowest-set-bit trick, but both are O(n) and equivalent in practice.
• When the naive version is fine. If n is tiny or the array is built once and reused, readability wins — the popcount loop is easier to read at a glance. The DP matters when n is large and the ×32 constant is a real cost, or when the interviewer wants the linear-time argument.
• vs. offset-of-power-of-two family. A third recurrence, ans[i] = ans[i - highestPowerOfTwo(i)] + 1, also works but needs you to track the current power of two; it is strictly more bookkeeping than recurrence A for the same complexity, so prefer A.

Edge cases & traps

• n = 0 returns [0] — a single base-case entry. The loop from 1 never runs, so you must size the array as n + 1 and rely on the zero default.
• Off-by-one on length. The array is n + 1 long because the range is inclusive of n. Sizing it n drops the last (and most-asked-about) entry.
• Operator precedence — and it differs by language. In Java, & binds looser than +, so ans[i>>1] + i & 1 parses as (ans[i>>1] + i) & 1 and silently produces garbage — you must write the parentheses. In Go the reverse is true: & sits at the multiplicative precedence level (with * / % << >>), tighter than +, so the same unparenthesized ans[i>>1] + i & 1 actually parses as ans[i>>1] + (i & 1) — correct by accident. Write ans[i >> 1] + (i & 1) in both anyway: it is right in either language and does not make the reader recall a precedence table.
• Signed shift is a non-issue here because every i is a non-negative loop index; i >> 1 shifts in a 0 regardless of arithmetic vs. logical shift.

Takeaways

• ans[i] = ans[i >> 1] + (i & 1): dropping the last bit lands on an already-solved smaller number, plus the parity of the bit you dropped.
• Recognizing that ans[i] depends on a smaller ans[·] is what turns an O(n·32) scan into an O(n) DP.
• A library-popcount loop is a legitimate production answer but skips the recurrence the problem is designed to elicit.
• Watch the inclusive length (n + 1) and parenthesize the mask.