Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every i from 0 to n. Try to do it in O(n) time without counting each number bit by bit.
0, 1 is 1, 2 is 10.- 0 <= n <= 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force counts the bits of every number from 0 to n, which is O(n log n). This is really a small DP. State: ans[i] is the number of 1 bits in i. Recurrence: shifting i right by one drops its last bit, giving a smaller number we already solved, so ans[i] = ans[i >> 1] + (i & 1). Base case: ans[0] = 0. Another valid recurrence is ans[i] = ans[i & (i - 1)] + 1, which removes the lowest set bit.
Algorithm
- Create
ansof sizen + 1filled with 0. - For
ifrom 1 ton:ans[i] = ans[i >> 1] + (i & 1). - Return
ans.
O(n)Space: O(1) besides the outputn + 1 entries, including 0. For n = 0 the answer is [0], not an empty list.class Solution: def countBits(self, n: int) -> List[int]: ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i >> 1] + (i & 1) # drop the last bit, add it back return ans