Given a non-negative number n and two values l and r. The problem is to count the number of set bits in the range l to r in the binary representation of n, i.e, to count set bits from the rightmost lth bit to the rightmost rth bit. Constraint: 1 <= l <= r <= number of bits in the binary representation of n. Examples:
Input : n = 42, l = 2, r = 5 Output : 2 (42)10 = (101010)2 There are '2' set bits in the range 2 to 5. Input : n = 79, l = 1, r = 4 Output : 4
We have existing solution for this problem please refer Count set bits in a range link. We can solve this problem quickly in Python. Approach is very simple,
- Convert decimal into binary using bin(num) function.
- Now remove first two characters of output binary string because bin function appends ‘0b’ as prefix in output string by default.
- Slice string starting from index (l-1) to index r and reverse it, then count set bits in between.
Python
# Function to count set bits in a range def countSetBits(n,l,r): # convert n into it's binary binary = bin(n) # remove first two characters binary = binary[2:] # reverse string binary = binary[-1::-1] # count all set bit '1' starting from index l-1 # to r, where r is exclusive print (len([binary[i] for i in range(l-1,r) if binary[i]=='1'])) # Driver programif __name__ == "__main__": n=42 l=2 r=5 countSetBits(n,l,r) |
Output:
2
Time Complexity : O(log n)
Auxiliary Space : O(log n)
Another Approach:
The set bits in the binary form of a number (obtained using the bin() method) can be obtained using the count() method.
Python3
# Function to count set bits in a rangedef countSetBits(n, l, r): # convert n into its binary form # using bin() # and then process it using string # slice methods binary = bin(n)[-1:1:-1] # count all set bit '1' starting from index l-1 # to r, where r is exclusive print(binary[l - 1: r].count("1"))# Driver Coden = 42l = 2r = 5countSetBits(n, l, r)#This code is contributed by phasing17 |
Output
2
Time Complexity : O(1)
Auxiliary Space: O(1)
