K'th Special Number in Range

Ninja
0/200
Average time to solve is 24m
profile
Contributed by
18 upvotes
Asked in companies
BNY MellonIntuitShareChat

Problem statement

Ninja wants to practice martial arts in order to master it but he has a pending school assignment and wants your help to solve it.

You are given two integers ‘L’ and ‘R’ denoting the range of integers [L, R]. A special number is a number that has (101)2 subarray in its binary representation. You have a simple task, you need to find the ‘K’th’ special number that lies in the given range, print -1 if it is not possible.

For Example : 
If L = 5 and R = 7, and you need to find the 1’st special number lying in the range [5, 7]

The answer for this is equal to 5, as 5 is the first special number lying in the given range, it is a special number because it has a subarray 101 in its binary representation.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains three integers ‘L’, ‘R’ and ‘K’ denoting the range and the lucky number to be calculated respectively.
Output Format : 
For each test case, print the K’th special number lying in the given range.

Output for each test case will be printed in 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 ≤ 10      
1 ≤ L ≤ R ≤ 50000
1 ≤ K ≤ 50000

Time limit: 1 sec
Sample Input 1 :
2
5 7 1
8 11 3
Sample Output 1 :
5
-1
Explanation For Sample Input 1 :
For test case 1 :
We will print 5 because:
5 is the first special number lying in the given range, it is a special number because it has a subarray 101 in its binary representation.

For test case 2 : 
We will print -1 because:
There are two special numbers lying in the range [8, 11], these are 10 = (1010)2 and 11 = (1011)2 as both of them have a subarray of 101 in their binary representation. As third special number doesn’t exist in this range, hence we will print -1.
Sample Input 2 :
2
1 10 2
1 5 1
Sample Output 2 :
10
5
Hint

Try to check each element in the range!

Approaches (2)
Brute Force

A simple straightforward approach is to check the binary representation of each number in the range, as soon as we have found the K’th special number we can print it.

 

The steps are as follows :

  1. Initialize a variable ‘cnt’ equal to 0, it will store the special numbers calculated so far.
  2. Run a for loop to iterate through each element in the range [L, R].
  3. For each element, check if (101)2 exists in its binary representation, the easiest way to do this is by directly using bitshifts ( ‘<<’ and ‘>>’ ) as they directly allow us to check if i’th bit is ON or OFF, in case you don’t know about them then free to do use some other method. If you are able to find a (101)2 subarray in the current number then increment the value of ‘cnt’ by one.
  4. If the value of ‘cnt’ is equal to ‘K’ then return the value of the current element in the range.
  5. If you have iterated through the entire range and were not able to find an answer then return -1.
Time Complexity

O( N * log(N) ), where N denotes the length of the range

 

In the worst-case, we might end up iterating through each element in the range and check its binary representation, checking the binary representation of each number is of order ~logN.

Hence the time complexity is O( N*log(N) ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
K'th Special Number in Range
Full screen
Console