Counting Bits

Given an integer `n`, return an array `ans` of length `n + 1` such that for each `i` (`0 <= i <= n`), `ans[i]` is the number of `1`'s in the binary representation of `i`. Can you do it in linear time `O(n)`? ### Constraints - `0 <= n <= 10^5` ### Input Format A single line containing the integer `n`. ### Output Format Print the `n + 1` space-separated integers.