You are provided with a non-negative integer n. Your task is to produce an integer array ans of length n + 1 such that, for every i in the inclusive range [0, n], ans[i] equals the total number of 1 bits present in the binary representation of i.
Example 1
Input: n = 3
Output: [0,1,1,2]
Explanation: The binary forms: 0 → 0, 1 → 1, 2 → 10, 3 → 11. Their respective set‑bit counts are 0, 1, 1, and 2.
Example 2
Input: n = 6
Output: [0,1,1,2,1,2,2]
Explanation: For i = 4, 5, and 6, the binary strings are 100, 101, and 110, which contain 1, 2, and 2 ones.
Example 3
Input: n = 0
Output: [0]
0 <= n <= 10^5A straightforward method that counts bits for each integer independently runs in O(n log n) time. Can you design an algorithm that fills the entire ans array in a single linear pass, achieving O(n) time, without relying on any built‑in function that counts set bits?