Description
For each integer from zero through n, return its number of set bits.
Solution
def count_bits(n):
result = [0]*(n+1)
for i in range(1,n+1):
result[i] = result[i >> 1] + (i & 1)
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[2]- Output
[0,1,1]
The binary forms are 0, 1, and 10.
Example 2
- Input
[0]- Output
[0]
The output still includes the count for zero.
Example 3
- Input
[5]- Output
[0,1,1,2,1,2]
Counts are listed for every value through five.
Approach
Reuse the count for the number shifted right and add its last bit.
Time & space
O(n) time; O(1) auxiliary space excluding O(n) output, where n is the upper bound of the requested range.