Problem

Given an integer n, generate and return an array with a length of n + 1.

Each element should contain the count of 1 bits in the binary representation of the integer i.

Can you make a solution that uses O(n) time complexity?

Examples

binaryOnesCount(3)
// return [0, 1, 1, 2]
/* Why?
0 -> 0
1 -> 1
2 -> 10
3 -> 11 */

binaryOnesCount(6)
// return [0, 1, 1, 2, 1, 2, 2]
/* Why?
0 -> 0
1 -> 1
2 -> 10
3 -> 11
4 -> 100
5 -> 101
6 -> 110 */