Guess Number Higher or Lower

Problem Statement

In the "Guess Game," we are tasked to determine a hidden number picked by the system within a known range from 1 to n. The game mechanics involve making guesses to identify this hidden number. Upon each incorrect guess, the system informs whether the pick is higher or lower compared to our guessed number. This interaction is facilitated through a predefined API int guess(int num), which can return:

• -1 indicating that the guessed number is higher than the pick (num > pick).
• 1 meaning the guessed number is lower than the pick (num < pick).
• 0 signifying that the guessed number exactly matches the pick (num == pick).

Given n, the upper limit of the range, and utilizing the guess API function, the goal is to efficiently determine the exact number chosen by the system.

Examples

Example 1

Input:

n = 10, pick = 6

Output:

6

Example 2

Input:

n = 1, pick = 1

Output:

1

Example 3

Input:

n = 2, pick = 1

Output:

1

Constraints

• 1 <= n <= 231 - 1
• 1 <= pick <= n

Approach and Intuition

To solve the "Guess Game" efficiently, given the structured behavior of the API responses, a binary search approach is suitable. The idea is to minimize the number of guesses by reducing the potential range of numbers strategically based on the feedback provided after each guess. Here’s a step-by-step approach using binary search:

1. Initialize two pointers – low starting at 1 and high starting at n to represent the current range of possible numbers.
2. Compute a middle point mid using the average of low and high. This mid-point is our current guess.
3. Call the guess(mid) API:
   • If the result is 0, the guess is correct, and mid is the number we're looking for.
   • If the result is -1, the target number is lower than mid. Adjust the high pointer to mid - 1 to narrow down the searching range to lower half.
   • If the result is 1, the target number is higher than mid. Adjust the low pointer to mid + 1 to focus the search on the upper half.
4. Repeat the guessing process, recalculating mid based on the updated low and high values until the correct number is found.

Intuition

The binary search approach effectively halves the number of possibilities with each guess, ensuring that the maximum number of guesses does not exceed ⌈log₂(n)⌉. This guarantees a prompt convergence to the correct number by logarithmically reducing the range of potential guesses, leveraging the directional feedback provided by the guess API. The method is both time-efficient and straightforward, harnessing the predictability and bounds provided by the game’s rules.

Solutions

/* The guess API is provided in the superclass GuessGame.
   @param numberToGuess, your guess number
   @return -1 if my number is smaller, 1 if my number is bigger, otherwise return 0
      int guess(int numberToGuess); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1;
        int end = n;
        while (start <= end) {
            int mid1 = start + (end - start) / 3;
            int mid2 = end - (end - start) / 3;
            int result1 = guess(mid1);
            int result2 = guess(mid2);
            if (result1 == 0)
                return mid1;
            if (result2 == 0)
                return mid2;
            else if (result1 < 0)
                end = mid1 - 1;
            else if (result2 > 0)
                start = mid2 + 1;
            else {
                start = mid1 + 1;
                end = mid2 - 1;
            }
        }
        return -1;
    }
}