Set Bits For Every Number
Problem
Given a non-negative whole number n, return a list whose entry at index i is the number of ones in the binary form of i, for every i from 0 up to n inclusive. Try to fill the whole list in a single pass without looping over the digits of each number.
Examples
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Why: 0, 1, 10, 11, 100, 101 in binaryInput: n = 2
Output: [0, 1, 1]Input: n = 0
Output: [0]
Why: edge case, the list still holds the entry for zero itselfHints
0 / 3
Counting the ones of every number from scratch repeats work. Some smaller number you have already handled looks almost exactly like the current one.
Shifting a number one place to the right drops its lowest digit and keeps every other digit. That smaller number is already in your list.
Fill the list from 1 upwards. The count for i is the count stored for i shifted right by one, plus one if the lowest digit of i is a one.
Solution
Dropping the lowest binary digit of i gives i shifted right by one, a smaller number whose count is already known, so the count for i is that stored count plus the dropped digit. Filling the list in increasing order guarantees every lookup points backwards to a finished entry. Each entry costs one shift, one AND and one addition. Time is O(n) and the output list is O(n) space.
def set_bits_up_to(n):
counts = [0] * (n + 1)
for i in range(1, n + 1):
counts[i] = counts[i >> 1] + (i & 1) # reuse the answer without the low digit
return counts
print(set_bits_up_to(5)) # -> [0, 1, 1, 2, 1, 2]
print(set_bits_up_to(2)) # -> [0, 1, 1]
print(set_bits_up_to(0)) # -> [0]Stuck on the idea rather than the code? Counting Set Bits covers it.