Counting Bits

Given a non-negative integer n, return an array where index i holds the number of set bits (1s) in the binary representation of i, for every i from 0 to n.

Example

Input: 5 Output: 0 1 1 2 1 2 (bit counts for 0,1,2,3,4,5)

Approach

Computing each value's bit count independently (like the previous problem) works but repeats effort. Instead, reuse previously computed answers: dp[i] = dp[i >> 1] + (i & 1). Right-shifting i by one bit drops its last bit, and that shifted value's bit count was already computed earlier in the same pass — just add back whether the dropped bit was a 1. One O(n) pass, no per-number bit-counting loop needed.

Input format

Line 1: n

Print dp[0..n], space-separated.