Guess Number Higher Or Lower - Leetcode Solution

Problem statement:

You are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API int guess(int num), which returns 3 possible results:

-1: The number I picked is lower than your guess (i.e. pick < num). 1: The number I picked is higher than your guess (i.e. pick > num). 0: The number I picked is equal to your guess (i.e. pick == num).

Return the number that I picked.

Solution:

The given problem can be solved using binary search. The basic idea is to find the mid-point of the search space and to determine whether to search in the left or the right part of the space based on the guess result. The search space will keep getting smaller with each guess until the number is found.

For the implementation, we will maintain two pointers, left and right, which will represent the start and end of the search space, respectively. We will then calculate the mid-point of the search space as (left+right)/2. We will then call the guess API with this mid-point and check its result. Depending on the result, we will either move the left pointer to mid+1 or the right pointer to mid-1. We will repeat this process until we find the number.

Here is the implementation:

public int guessNumber(int n) {
    int left = 1;
    int right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int result = guess(mid);
        if (result == 0) {
            return mid;
        } else if (result == 1) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Number not found
}

In the above implementation, we start by setting the left pointer to 1 and the right pointer to n, which represents the initial search space. We then enter a while loop and calculate the mid-point using the formula (left+right)/2. We then call the guess API with this mid-point and check its result. If the result is 0, we have found the number and we return it. If the result is 1, we set the left pointer to mid+1, which means we need to search in the right part of the search space. If the result is -1, we set the right pointer to mid-1, which means we need to search in the left part of the search space. We then repeat this process until we find the number.

Time Complexity: O(log n), where n is the size of the search space.

Space Complexity: O(1), as we are not using any extra space apart from the two pointers.

1