Counting Bits

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1s in the binary representation of i.

Examples

Example 1:

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

Example 2:

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation:
  0 --> 0     (zero 1s)
  1 --> 1     (one 1)
  2 --> 10    (one 1)
  3 --> 11    (two 1s)
  4 --> 100   (one 1)
  5 --> 101   (two 1s)

Constraints

• 0 <= n <= 10^5

Follow Up

• Can you solve it in O(n) time and O(n) space (not counting the output array)?
• Can you do it without using any built-in popcount functions?

Expected Complexity

• Time: O(n)
• Space: O(n)