424. 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 tasks you with determining the count of 1s in the binary representation of each number up to a given number N. Your objective is to create an array ans of length n + 1, where ans[i] represents the number of 1s in the binary form of i (0 <= i <= n). Can you accomplish this in linear time O(n) and without utilizing any built-in functions?
Input Format
The first line contains an integer N, indicating the size of the array.
Output Format
Print an array ans, where each ans[i] represents the number 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