Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def find(n):
- if x==0 or x==1:
- return x
- n=math.log2(x)
- n=int(n)
- ```
- This problem can be converted to count set bita in first x+1 whole numbers
- Find max greatest power of 2 less than or equal to x.
- Since its a power of 2 we can compute it easily using the following formula.
- 2**n*(n/2) no of bits from 0 to 2**n-1
- Then we shall reduce space from 2**n to x
- from 2**n to x first bit will be 1
- ```
- t=2**n*n//2+(x-2**n+1)+find(x-2**n)
- return int(t)
- class Solution:
- #Function to return sum of count of set bits in the integers from 1 to n.
- def countSetBits(self,n):
- return find(n)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement