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 set bits (1s) in the binary representation of i.

Example 1:

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

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation: 0,1,10,11,100,101

Constraints:

• 0 ≤ n ≤ 10⁵

Follow-up: Can you do it in O(n) time, and possibly in a single pass?