Count set bits
Your task
Given an integer n (0 <= n <= 1e5), return a list ans of length n+1 where ans[i] is the number of set bits (1s) in the binary representation of i. Aim for O(n) total time using the relationship between i and a smaller, already-computed value (no per-number popcount loop).
Examples
count_bits(n: int) -> list[int]Example 1
Input
count_bits(2)Output
[0, 1, 1]