Given a non-negative integer n, build an array ans with n + 1 entries, one for each integer from 0 up to n. Entry ans[i] must hold the number of 1 digits in the binary form of i. Return ans.
Counting the bits of each number separately takes O(n log n) time. Try for O(n): the count for i can be built from a count you have already worked out. And try it without a built-in bit-counting function.
In binary, 0, 1, 2, 3 are 0, 1, 10, 11.
7 is 111, so it has three 1s. One step later, 8 is 1000 and has only one.
The array still has n + 1 = 1 entry: zero has no 1 digits at all.
Constraints
0 <= n <= 10⁵Dropping the last binary digit of i gives i >> 1 (that is, i / 2): a smaller number whose count you have already worked out.
You need a count for every number from 0 to n, not just one. That's the hint: the numbers share most of their binary digits with smaller numbers, whose counts you will already have.
Time O(n)Space O(1) extra
The full walkthrough and code are part of Premium
3