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 (the number I picked stays the same throughout the game).
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.
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
My Solution
We can solve this problem with binary search. We start with our start pointer equal to 1 and our end pointer equal to n. We find the midpoint and guess the number. If we found the number we return it. Otherwise we update our start and end pointers accordingly.
Time complexity is O(log n) because of binary search. Space complexity is O(1) since we only require constant extra space.
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is higher than the picked number
* 1 if num is lower than the picked number
* otherwise return 0
* int guess(int num);
*/
public class Solution extends GuessGame {
public int guessNumber(int n) {
int start = 1;
int end = n;
while (start <= end) {
int mid = start + (end-start)/2;
if (guess(mid) == 0) {
return mid;
}
else if (guess(mid) == -1) {
end = mid-1;
}
else {
start = mid+1;
}
}
return start;
}
}