Odometer Bit Tally Sequence

EasyBit-ManipulationPopcountDynamic-Programming5 hidden tests

A binary odometer counts up from 0. For each reading i from 0 to n inclusive, report how many 1 bits appear in the binary representation of i.

Input format

Line 1: an integer n.

Output format

n + 1 space-separated integers on one line: for each i from 0 to n, the number of set bits in i, in increasing order of i.

Constraints

0 <= n <= 100000

Examples

Example 1

Input

Expected

0 1 1 2 1 2

Explanation

0->0, 1->1, 2(10)->1, 3(11)->2, 4(100)->1, 5(101)->2, giving 0 1 1 2 1 2.

Example 2

Input

Expected

Explanation

Only reading 0, which has no set bits.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →