Guess Number Higher or Lower
A number is picked from 1 to nguess(num)
: your guess is higher than the picked number;-1 : your guess is lower than the picked number;1 : your guess is correct.0
Return the picked number. This is LeetCode 374.
Example 1
Output: 6
Example 2
Output: 1
How to Think About It
Step 1: This is the guessing game everyone knows
With "higher" and "lower" hints, the best strategy is to guess the middle of what is left. Each answer rules out half of the remaining numbers. From 1 to 100, it never takes more than 7 guesses, because 27 = 128.
Step 2: Map the hints to the search range
- Start with
andlo = 1 .hi = n means mid is too high, so the number is below it:guess(mid) == -1 .hi = mid - 1 means mid is too low:guess(mid) == 1 .lo = mid + 1 : returnguess(mid) == 0 .mid
The signs are the easy part to get backwards: the API describes your guess compared with the pick, not the other way round.
Step 3: Watch the overflow
nlohi(lo + hi) / 2lo + (hi - lo) / 2
Walkthrough
n = 10, pick = 6:
| lo | hi | Guess (mid) | Answer | Next range |
|---|---|---|---|---|
| 1 | 10 | 5 | 1: too low | 6 to 10 |
| 6 | 10 | 8 | -1: too high | 6 to 7 |
| 6 | 7 | 6 | 0: correct | return 6 |
Java Solution
On LeetCode, guessguess
public class GuessNumberHigherLower {
private final int pick; // the hidden number (LeetCode hides this)
GuessNumberHigherLower(int pick) {
this.pick = pick;
}
// -1: the guess is too high, 1: too low, 0: correct
int guess(int num) {
return Integer.compare(pick, num);
}
public int guessNumber(int n) {
int lo = 1;
int hi = n;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // n can be 2^31 - 1, so (lo + hi) would overflow
int answer = guess(mid);
if (answer == 0) {
return mid;
} else if (answer < 0) {
hi = mid - 1; // our guess is too high
} else {
lo = mid + 1; // our guess is too low
}
}
return -1; // not reached for a valid game
}
public static void main(String[] args) {
System.out.println(new GuessNumberHigherLower(6).guessNumber(10)); // 6
System.out.println(new GuessNumberHigherLower(2147483647).guessNumber(2147483647));
// 2147483647
}
}
The original implementation,
Complexity
- Time: O(log n) calls to
: at most 31 for anyguess range.int - Space: O(1).