← All coding problems
Counting Bits
easyBit Manipulation+10 XPTime limit 2s
For every number i from 0 to n, print how many 1 bits it has.
Input: one integer n.
Output: n + 1 numbers on one line.
Constraints: 0 ≤ n ≤ 10⁵.
Challenge: do it in O(n) without counting bits one by one: bits[i] = bits[i >> 1] + (i & 1) — shifting right drops the last bit, which you then add back.
Sample input 1
2
Sample output 1
0 1 1
Sample input 2
5
Sample output 2
0 1 1 2 1 2
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).