374. Guess Number Higher or Lower

Description

We 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 will tell you whether the number I picked is higher or lower than your guess.

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

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

Return the number that I picked.

Guess Number Higher or Lower

We 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 will tell you whether the number I picked is higher or lower than your guess.

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

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

Return the number that I picked.

Intuition

The problem is a classic example of a binary search problem. The key observation is that each response from the guess API helps to eliminate half of the search space, which makes the binary search approach particularly efficient.

Approach

1. Initialize the Search Space: Start with the full range from 1 to n.
2. Binary Search: - Compute the middle point of the current range. - Use the guess API to check if the middle point is the correct number. - If the result is 0, then the middle point is the correct guess. - If the result is -1, the correct number is smaller, so adjust the right boundary to mid - 1. - If the result is 1, the correct number is larger, so adjust the left boundary to mid + 1.
3. Repeat the Process: Continue the process until the correct number is found.

Complexity

Time Complexity:

O(log n) - Each guess reduces the search space by half, leading to a logarithmic number of guesses.

Space Complexity:

O(1) - The algorithm only uses a few variables for the search boundaries and the middle point, making the space usage constant.

Code

C++

class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int result = guess(mid);

            if (result == 0) {
                return mid;
            } else if (result > 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

Python

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left <= right:
            mid = (left + right) // 2
            result = guess(mid)

            if result == 0:
                return mid
            elif result > 0:
                left = mid + 1
            else:
                right = mid - 1

        return -1

Java

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int result = guess(mid);

            if (result == 0) {
                return mid;
            } else if (result > 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function (n) {
    let right = n
    let left = 0
    while (left <= right) {
        let mid = Math.floor((right + left) / 2)

        const result = guess(mid)
        if (result > 0) {
            left = mid + 1
        } else if (result < 0) {
            right = mid
        } else {
            return mid
        }
    }

    return -1
};