Write ones_table(n: int) -> list[int] that returns a list table of length n + 1 where table[i] is the number of 1 digits in the binary form of i, for every i from 0 to n.
ones_table(3) # [0, 1, 1, 2]
ones_table(6) # [0, 1, 1, 2, 1, 2, 2]
ones_table(0) # [0]
Constraints:
0 <= n <= 10^6.
Counting the digits of each number from scratch costs O(n log n). Aim for O(n) in total: each entry should take constant work.
Show hint
every number i > 0 is a smaller number with one extra binary digit added at the end, or with one 1 removed. If that smaller number's entry is already in the table, you only need to adjust by 0 or 1.