Hamming Weights of Integers

Given a non-negative integer n, return an array ans of length n + 1 such that ans[i] is the number of set bits (1s) in the binary representation of i, for every i from 0 to n.

The number of set bits in an integer's binary representation is often called its "Hamming weight" or "popcount".

Your solution should avoid recomputing the popcount of each number from scratch (which would cost O(n log n) overall); instead, use previously computed entries of ans to compute each new entry in O(1) time, for O(n) total time.

Example 1

Input: n = 2
Output: [0, 1, 1]
Explanation:
  0 --> 0  (binary: 0)
  1 --> 1  (binary: 1)
  2 --> 1  (binary: 10)

Example 2

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation:
  0 --> 0  (000)
  1 --> 1  (001)
  2 --> 1  (010)
  3 --> 2  (011)
  4 --> 1  (100)
  5 --> 2  (101)

Constraints

• 0 <= n <= 10^5
• Follow-up: can you solve it in a single pass, using only O(1) extra space besides the output array?