Last Updated: 8 Jan, 2022

Guess The Number

Easy

Asked in companies

Solve now

Problem statement

You are given an integer ‘N’ and there is a hidden number in the range [0, N] which you have to guess. You are also given a function higherLower(k) to help you in guessing the number. The ‘higherLower(k)’ will return -1, 0 or 1, depending on if ‘k’ is smaller, equal or greater than the hidden number.

For Example:

You are given ‘N’ = 20, and the hidden number is ‘8’. You won't have access to the hidden number and you will have to guess the number ‘8’ using the higherLower function and print it.

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and the hidden number.

Output Format:

For each test case, print a single integer representing the hidden number.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
1 <= N <= 10^9
1 <= hidden number <= N

Time Limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, we will iterate through every number from 1 until higherLower(n) is equal to 0. Then we return ‘n’ where higherLower(n) is 0.

Algorithm:

Iterate num from 1 to N
- If higherLower(num) is equal to 0 return num
Otherwise return -1

Solve now

02 Approach

In this approach, we can see that if our guess is less than the hidden number, all the numbers smaller than the guess can’t be the answer. Similarly, if our guess is more than the hidden number all the numbers larger than our guess can’t be the answer so we can binary search our guess on all the numbers from 1 to ‘N’.

Algorithm:

Set high and low as N and 1 respectively.
While low is not greater than high
- Set guess as high + low / 2
- Set res as higherLower(guess)
- If res is less than 0 then set high as guess - 1
- Otherwise, if res is more than 0 set low as guess + 1
- Otherwise, return guess
Return -1, in guess is not found

Solve now