Understanding Counting Bits
Return an array where entry i is the number of set bits in the binary representation of i, for every integer from 0 through n.
How it works
Remove the last bit and reuse the answer for the remaining higher bits.
Initialize counts[0] to zero. For each i, reuse counts[i >> 1]. Add the low bit i & 1.
Try an example
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Remove the last bit and reuse the answer for the remaining higher bits.
Constraints
- n is an integer from 0 through 63.
- The output includes 0, whose set-bit count is 0.
Use the simulator
Change the input, then choose Visualize input. Use Next and Previous to inspect each decision, or Play to advance automatically. Compare approaches and their complexity. Choose Try yourself to write JavaScript, select My code and Visualize code to inspect its execution, or Run Tests to check results.
Execution happens in your browser. Drafts are saved locally; avoid entering secrets or sensitive information.