Counting Bits
For every i from 0 to n, return the number of 1 bits in i.
A way to picture it
Every number is a smaller number wearing one extra bit on its tail. Chop the tail off (i >> 1) and you get a number you've already counted. Add 1 back if the tail bit was a 1.
How to approach it
bits(i) = bits(i >> 1) + (i & 1). Each answer reuses one you computed earlier.
Example
Input: {"n":2}. Output: [0,1,1].
Complexity: O(n) time and O(n) space. Constant work per number, plus the output array.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.