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 to n.
Your algorithm must run in O(n) time and must not use a built-in population-count function.
Examples
Example 1
Input: n = 2
Output: [0, 1, 1]
Explanation: 0 is 0, 1 is 1, 2 is 10 in binary.
Example 2
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 0, 1, 10, 11, 100, 101 have 0, 1, 1, 2, 1, 2 set bits.
Constraints
0≤n≤105
Examples
Example 1
Input
n = 2
Output
[0, 1, 1]
Example 2
Input
n = 5
Output
[0, 1, 1, 2, 1, 2]
Loading editor...
Click "Run" to test with sample cases or "Submit" to run all tests.