Bit ManipulationDynamic Programming
For every number i from 0 to n, count the 1 bits in its binary form. Print all n + 1 counts. Try to compute the whole list in O(n) time instead of counting bits for each number separately.
Input
A single integer n.
Output
Print n + 1 integers: the number of 1 bits of 0, 1, 2, ..., n.
Constraints
0 <= n <= 50000
Example 1
Input
5
Output
0 1 1 2 1 2
0, 1, 2, 3, 4, 5 have 0, 1, 1, 2, 1, 2 set bits.