Program to count total number of set bits of all numbers in range 0 to n in Python

Suppose we have a number num. For each numbers i in the range 0 ≤ i ≤ num we have to calculate the number of 1's in their binary counterpart and return them as a list. So if the number is 5, then the numbers are [0, 1, 2, 3, 4, 5], and number of 1s in these numbers are [0, 1, 1, 2, 1, 2], so it will return 7.

To solve this, we will follow these steps −

• res := an array which holds num + 1 number of 0s

• offset := 0

• for i in range 1 to num + 1

  • if i and i − 1 = 0, then res[i] := 1 and offset := 0

  • else increase offset by 1 and res[i] := 1 + res[offset]

• return sum of the elements of res

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:    def countBits(self, num):       result = [0] * (num+1)       offset = 0       for i in range(1,num+1):          if i & i-1 == 0:             result[i] = 1             offset = 0          else:             offset+=1             result[i] = 1 + result[offset]       return sum(result) ob1 = Solution() print(ob1.countBits(5))

Input

5

Output

7