Guess Number Higher or Lower

Updated on 02 June, 2025
Guess Number Higher or Lower header image

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

  • Java
java
/* 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;
    }
}

In the given Java implementation, the task is to guess a secret number within a predefined range using a ternary search approach, optimizing the classic binary search algorithm.

  1. The method guessNumber(int n) aims to find a mystery number between 1 and n. The method guess(int numberToGuess) is utilized to make a comparison against the secret number.
  2. Two pointers, start and end, are initialized to the beginning and end of the range, respectively.
  3. Within a while loop, as long as start is less than or equal to end, the method calculates two middle points, mid1 and mid2, effectively dividing the current range into three parts.
  4. Two guesses are then made using mid1 and mid2.
  5. If any of the guesses returns 0, it indicates that the right number has been guessed, and this number is immediately returned.
  6. If result1 is -1, then the search area adjusts to the left section by setting end to mid1 - 1.
  7. Conversely, if result2 is 1, the search area shifts to the right section by setting start to mid2 + 1.
  8. If neither of the above conditions are met, the search narrows down to the section between mid1 + 1 and mid2 - 1.
  9. If the loop completes without returning the number, -1 is returned indicating the number was not found within the range.

This approach decreases the number of comparisons in a large range, thereby enhancing the efficiency over traditional binary search, especially when the range of numbers is significantly large.

Comments

No comments yet.