Guess The Number
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

Question

Guess The Number

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.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1),

We are not using any extra space.

Time Complexity: O(n)Explanation:

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

Java (SE 1.8)


/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where N is the integer given.
*/

public class Solution {

	public static int numberGuess(int n, Guesser guesser) {

		for (int num = 1; num < n + 1; num++) {

			// If the number is found return the answer.
			if (guesser.higherlower(num) == 0) {
				return num;
			}
		}

		// Return -1, Never reach here.
		return -1;
	}
}

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where N is the integer given.
'''

def numberGuess(n: int, guesser) -> int:


    for num in range(1, n + 1):

        # If the number is found return the answer.
        if guesser.higherlower(num) == 0:
            return num

    # Return -1, Never reach here.
    return -1

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where N is the integer given.
*/

int numberGuess(int n, Guesser guesser){

    for(int num = 1; num < n + 1; num++){

        // If the number is found return the answer.
        if(guesser.higherlower(num) == 0){
            return num;
        }
    }

    // Return -1, Never reach here.
    return -1;
}

Accepted Answer

Binary Search

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

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra space.

Time Complexity: O(logn)Explanation:

O(log(N)), Where N is the integer given

We are performing a binary search on the range 1 to N, which will cost O(log(N)) time. Hence the final time complexity is O(log(N)).