Two Zeroes

Moderate
0/80
profile
Contributed by
1 upvote

Problem statement

A number ‘X’ is interesting if the binary representation of ‘X’ (without leading zeroes) has exactly two zeroes.

You are given two positive integers, ‘L’ and ‘R’. Your task is to count the number of values ‘X’, such that ‘L’ ≤ ‘X’ ≤ ’R’ and ‘X’ is interesting (i.e., it has exactly two zeroes in its binary representation).

Example : 
L = 2, R = 9
All the numbers between L and R and their binary representations are:
X = 2 => 10
X = 3 => 11
X = 4 => 100
X = 5 => 101
X = 6 => 110
X = 7 => 111
X = 8 => 1000
X = 9 => 1001
As 4 and 9 are the only numbers with two zeroes in their binary representations, hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains two space-separated integers, ‘L’ and ‘R’, denoting the range in which you have to find interesting integers.
Output Format : 
For each test case, count the number of values ‘X’, such that ‘L’ ≤ ‘X’ ≤ ’R’ and ‘X’ has exactly two zeroes in its binary representation.

Output for each test case will be printed on a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 30
1 ≤ L ≤ R ≤ 10^9

Time limit: 1 sec
Sample Input 1 :
2
1 6
3 11
Sample Output 1 :
1
3
Explanation For Sample Input 1 :
For test case 1: 
All the numbers between 1 and 6 and their binary representations are:
X = 1 => 1
X = 2 => 10
X = 3 => 11
X = 4 => 100
X = 5 => 101
X = 6 => 110
As 4 is the only number with two zeroes in its binary representation, hence the answer is 1.

For test case 2:
All the numbers between 3 and 11 and their binary representations are:
X = 3 => 11
X = 4 => 100
X = 5 => 101
X = 6 => 110
X = 7 => 111
X = 8 => 1000
X = 9 => 1001
X = 10 => 1010
X = 11 => 1011
As 4, 9, and 10 are the only numbers with two zeroes in their binary representations, hence the answer is 3.
Sample Input 2 :
2
11 16
10 20
Sample Output 2 :
1
3
Hint

Try all possible integers.

Approaches (2)
Brute Force Approach

 

Approach: 

 

  • We can try all possible integers ‘X’ such that ‘L’ ≤ ‘X’ ≤ ’R’ and then check if it has exactly two zeroes in its binary representation or not.
  • See the algorithm section below to find out how to check if ‘X’ has exactly two zeroes.
     

Algorithm: 

 

  • Declare and initialize a variable ‘ans’ to ‘0’.
  • Iterate over all the integers from ‘L’ to ‘R’. Let the iterating variable be ‘i’.
  • Declare and initialize a boolean variable ‘st’ to ‘false’.
  • Declare and initialize an integer variable ‘cnt’ to ‘0’.
  • Iterate over bit position from 30 to 0.
    • Check if the bit is high. If it’s high, set ‘st’ to ‘true’.
    • Now, if ‘st’ is ‘true’, and the current bit is not high, increment ‘cnt’ by 1.
  • If the value of ‘cnt’ is 2, then increment ‘ans’ by 1.
  • Finally, return the answer ‘ans’.
Time Complexity

O(R - L)

 

We iterate over all the possible integers between the range [‘L’, R’], and check in constant time if this has exactly two zeroes in its binary representation or not.

 

Hence, the time complexity is O(R - L).

Space Complexity

O(1)
 

We only store variables that use constant extra space.

 

Hence, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Two Zeroes
Full screen
Console