Easy · Bit Manipulation · about 10 minutes
Asked at Apple, Amazon, Google.
For every integer i from 0 through n, count the 1s in its binary form. Return the counts as an array of n + 1 numbers, in O(n) total time.
i
n
n + 1