Foundations
Counting Bits
Return the popcount for every integer from 0 to n in O(n) time - popcount(i) = popcount(i >> 1) + (i & 1) reuses already-computed results by linking each number to its right-shifted half.
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.
Example 1:
Input: n = 4
Output: [0, 1, 1, 2, 1]Example 2:
Input: n = 8
Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]Constraints:
0 <= n <= 10^5
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 Breakdown
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 = 8 = 1000. 8 >> 1 = 4 = 100, whose count ans[4] is 1, and 8 & 1 = 0 since 8 is even, so ans[8] = 1 + 0 = 1. For i = 7 = 111, 7 >> 1 = 3, ans[3] = 2, and 7 & 1 = 1, giving ans[7] = 3. 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.
Done reading? Mark it so it sticks in your dashboard.