Guess The Number

Easy

0/40

Contributed by

6 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
20 8
5 2

Sample Output 2:

8
2

Explanation:

For the first test case, ‘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’ and print it.

For the second test case ‘N’ = 5, and the hidden number is ‘8’. You won't have access to the hidden number and you will have to guess the number ‘8’ and print it.

Sample Input 2:

2
10 10
100 1

Sample Output 2:

 10
 1

Hint 1

Hint 2

Try every number starting with 1

Approaches (2)

Approach 1

Approach 2

Linear Search

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

Time Complexity

O(N), Where N is the integer given

We are iterating from 1 to N which will cost O(N) time. Hence the final time complexity is O(N).

Space Complexity

O(1),

We are not using any extra space.

(100% EXP penalty)

Guess The Number

Console