
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:
- Initialize two pointers –
low
starting at1
andhigh
starting atn
to represent the current range of possible numbers. - Compute a middle point
mid
using the average oflow
andhigh
. This mid-point is our current guess. - Call the
guess(mid)
API:- If the result is
0
, the guess is correct, andmid
is the number we're looking for. - If the result is
-1
, the target number is lower thanmid
. Adjust thehigh
pointer tomid - 1
to narrow down the searching range to lower half. - If the result is
1
, the target number is higher thanmid
. Adjust thelow
pointer tomid + 1
to focus the search on the upper half.
- If the result is
- Repeat the guessing process, recalculating
mid
based on the updatedlow
andhigh
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
/* 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.
- The method
guessNumber(int n)
aims to find a mystery number between 1 andn
. The methodguess(int numberToGuess)
is utilized to make a comparison against the secret number. - Two pointers,
start
andend
, are initialized to the beginning and end of the range, respectively. - Within a while loop, as long as
start
is less than or equal toend
, the method calculates two middle points,mid1
andmid2
, effectively dividing the current range into three parts. - Two guesses are then made using
mid1
andmid2
. - If any of the guesses returns 0, it indicates that the right number has been guessed, and this number is immediately returned.
- If
result1
is -1, then the search area adjusts to the left section by settingend
tomid1 - 1
. - Conversely, if
result2
is 1, the search area shifts to the right section by settingstart
tomid2 + 1
. - If neither of the above conditions are met, the search narrows down to the section between
mid1 + 1
andmid2 - 1
. - 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.
No comments yet.