# 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

Output:

8

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))

**Input/Output:**

1.

Enter lower limit: 0 Enter upper limit: 7 The no of set bits: 8

2.

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.

**Time Complexity:**

O(1)

You may also read:

## Leave a Reply