817. Henry's Binary Revolution
0
Medium
King Henry VIII desires to break away from the catholic church and revolutionize the decimal system. He seeks to implement the binary number system and assigns you the task of determining the number of 1s in the binary representation of each number up to a given value N. Your objective is to create an array ans of length n + 1, where ans[i] represents the count of 1s in the binary form of i (0 <= i <= n). It is crucial to devise a solution with a runtime of O(n) and preferably in a single pass, without utilizing any built-in functions like __builtin_popcount in C++.
Input Format
The first line of input consists of an integer N, indicating the size of the array.
Output Format
Print an array ans, where each ans[i] represents the count of 1s in the binary representation of i.
Example
Input
5
Output
0 1 1 2 1 2
Constraints
0 <= n <= 10^5
Loading...
View Submissions
Console