Blind 75 · Bit Manipulation
Given an integer n, return an array answer of length n + 1 where answer[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.
The expected solution computes each entry from earlier entries rather than counting every number from scratch.
Example 1: Input: n = 2 Output: [0,1,1] Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0,1,10,11,100,101. Example 3: Input: n = 0 Output: [0]
0 <= n <= 10^5
Binary and two's complement — how a negative number is stored, and what a shift does at the edges.
The trick worth memorising: n & (n-1) clears the lowest set bit.
Every number is some smaller number with one extra bit on the end: i has the bits of i >> 1, plus one if i is odd. Since i >> 1 is always smaller than i, its answer is already computed — one lookup and one addition per number, instead of counting each from scratch.
1. bits[0] is zero.
2. For each i, bits[i] = bits[i >> 1] + (i & 1).
Time O(n). Space O(n) for the output. Per-number popcount is O(n log n), which this beats.