Count the no of Set Bits between L and R for only prime positions in Python
You are given two integers- lower limit(L) and upper limit(R). You have to find the no of set bits in the binary representation of the numbers between L and R (both inclusive) for only prime positions.
Eg. L=0, R=7
The explanation is for only 9 bits. But we will implement for 32 bits. So, now we will see how to solve the problem.
Counting the no of Set Bits between L and R for only prime positions
We will see the algorithm, program and time complexity of the program.
Algorithm for optimal solution:
- Take the prime positions up to 32 in a list.
- You can notice that for position 2, for every 4 (i.e 2^2) numbers there are 2 (i.e 2^1) set bits. Similarly, for position 3, for every 8 (i.e 2^3) numbers there are 4 (i.e 2^2) set bits and so on. So, for the position n, for every 2^n numbers, there are 2^(n-1) set bits.
- Following the above logic, you have to calculate the total no of set bits for every prime position from 0 to R and 0 to (L-1).
- Now, Subtract the two results to get the actual output.
Python Program for the problem:
prime_pos=[2,3,5,7,11,13,17,19,23,29,31] #List of prime positions lower=int(input("Enter lower limit: ")) #Take Lower limit from user upper=int(input("Enter upper limit: "))#Take Upper limit from user def calculate(n): tot_set_bit=0 for i in prime_pos: #Iterate for every prime position cycle=2**i set_bit=cycle//2 tot_set_bit+=((n+1)//cycle)*set_bit if((n+1)%cycle>set_bit): tot_set_bit+=(n+1)%cycle-set_bit return tot_set_bit ''' Call the function for R(upper) and for (L-1)(lower) and subtract the result''' print("The no of set bits:",calculate(upper)-calculate(lower-1))
Enter lower limit: 0 Enter upper limit: 7 The no of set bits: 8
Enter lower limit: 4 Enter upper limit: 20 The no of set bits: 22
The code is only the implementation of the above algorithm. In the above code, tot_set_bit counts the total no of set bits. For every 2^n numbers (denoted by the variable cycle) there are 2^(n-1) set bits (denoted by set_bit) where n denotes the prime position.
You may also read:
Leave a Reply