Advertisement
Iam_Sandeep

Count set bits for first N numbers

Jun 14th, 2022
1,205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.66 KB | None | 0 0
  1. def find(n):
  2.     if x==0 or x==1:
  3.         return x
  4.     n=math.log2(x)
  5.     n=int(n)
  6.     ```
  7.     This problem can be converted to count set bita in first x+1 whole numbers
  8.     Find max greatest power of 2 less than or equal to x.
  9.     Since its a power of 2 we can compute it easily using the following formula.
  10.     2**n*(n/2) no of bits from 0 to 2**n-1
  11.     Then we shall reduce space from 2**n to x
  12.     from 2**n to x first bit will be 1
  13.     ```
  14.     t=2**n*n//2+(x-2**n+1)+find(x-2**n)
  15.     return int(t)
  16. class Solution:
  17.     #Function to return sum of count of set bits in the integers from 1 to n.
  18.     def countSetBits(self,n):
  19.         return find(n)
  20.        
  21.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement