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.