Counting Bits

Problem

Compression codecs and Huffman encoders compute the population count for every symbol value in a range to build frequency tables. Given a non-negative integer n, return an array ans of length n+1 where ans[i] is the number of 1-bits in i, for every i from 0 to n inclusive.

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

Verification

Trace the first few values by hand before running: ans[0]=0 (base), ans[1]=ans[0]+1=1, ans[2]=ans[1]+0=1, ans[3]=ans[1]+1=2, ans[4]=ans[2]+0=1, ans[5]=ans[2]+1=2. Writing out i >> 1 and i & 1 side by side for i=1..8 makes the recurrence immediately obvious.

Solution

Approach - Dynamic programming on the right-shifted subproblem.

The set-bit count of i relates cleanly to a smaller, already-solved number: i >> 1 is i with its lowest bit dropped, and dropping a bit removes either a 0 or a 1. That dropped bit is exactly i & 1 - 1 when i is odd, 0 when i is even. So popcount(i) = popcount(i >> 1) + (i & 1). Allocate ans = [0] * (n + 1), leave ans[0] = 0 as the base case, and fill forward from i = 1. Because i >> 1 is always strictly less than i, ans[i >> 1] is already computed by the time the loop reaches i, so each entry is filled in O(1) by a single table lookup plus the parity bit.

Trace i = 5 = 101. 5 >> 1 = 2 = 10, whose count ans[2] is 1, and 5 & 1 = 1 since 5 is odd, so ans[5] = 1 + 1 = 2. For i = 4 = 100, 4 >> 1 = 2, ans[2] = 1, and 4 & 1 = 0, giving ans[4] = 1. This reuse is the whole win: calling a standalone Kernighan popcount for each number would cost O(n log n) across the range, while linking each value to its half collapses the total to O(n).

Edge cases - n = 0 returns [0]; the loop body never runs and the base case stands. Forward iteration order is required so the i >> 1 dependency is always already filled.

Complexity - O(n) time, O(1) extra space - each of the n+1 entries is one lookup, and the output array is the required result, not auxiliary storage.