#163EasyBit Manipulation· Population Count with DP

Bit Count Table

A compression library speeds up its encoder with a lookup table that stores, for every number from 0 up to `n`, how many 1 bits appear in its binary representation (its population count). Building the table by counting bits of each number separately costs O(n log n); the library wants a version that does a constant amount of work per entry. Given `n`, return an array `table` of length `n + 1` where `table[i]` is the number of 1 bits in `i`.

Input format

`n`: a non-negative integer.

Output format

An array of `n + 1` integers; entry `i` is the number of 1 bits in the binary form of `i`.

Examples

Input: n = 5

Output: [0, 1, 1, 2, 1, 2]

0 = 0, 1 = 1, 2 = 10, 3 = 11, 4 = 100, 5 = 101 in binary, which have 0, 1, 1, 2, 1, 2 one-bits.

Input: n = 0

Output: [0]

Only the number 0 is in range and it has no 1 bits.

Input: n = 8

Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]

Powers of two have a single 1 bit, so entries 1, 2, 4 and 8 are all 1. 7 = 111 has three.

Constraints

0 <= n <= 10^5

#bit-manipulation
#dynamic-programming
#arrays