Counting Bits

easyBit ManipulationDP: bits(i) = bits(i >> 1) + (i & 1)B75Solve on LeetCode#338

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 up to and including n.

Counting the bits of each number independently is easy but costs O(log i) work per number. The real question is the follow-up: fill the whole array in O(n) total time, doing O(1) work per entry, by reusing counts you have already computed.

Examples

Input:: n = 2
Output:: [0, 1, 1]

0 is 0b0 (zero 1s), 1 is 0b1 (one 1), 2 is 0b10 (one 1).

Input:: n = 5
Output:: [0, 1, 1, 2, 1, 2]

For example 3 is 0b11 with two 1s, and 5 is 0b101 with two 1s.

Hints

One at a time — struggle first, peek second.

Your thinking space — verify on LeetCode, then mark it.