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.
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.
Input: n = 10, pick = 6
Output: 6
Input: n = 1, pick = 1
Output: 1
Input: n = 2, pick = 1
Output: 1
Constraints:
- 1 <= n <= 231-1
- 1 <= pick <= n
Contents
- Solution 1 - Using binary search
In this approach, we will apply Binary Search algorithm,
since the input array is sorted in ascending order, we will use two pointers left and right to point to left and right boundary of values,
which are 1 and n respectively, and then using a while loop, compute the middle number
mid =
, then check what is the answer we get for this guess by calling guess(mid), based on the answer returned from thsi function, we can draw three conclusions.
-
If the answer is 0, that means the guess is correct, so return mid value.
-
If the answer is -1, that means the guess is higher than pick,
this means that the pick shoud be on between 1 and mid-1 range, so we will update right to mid-1.
-
If the answer is 1, that means the guess is lower than pick,
this means that the pick shoud be on between mid+1 and n range, so we will update left to mid+1.
public class GuessNumberHigherLower extends GuessGame {
public GuessNumberHigherLower(int n) {
init(n);
}
public int guessNumber(int n) {
int left = 1;
int right = n;
while(left<=right) {
int mid = left + (right - left) /2;
int guess = guess(mid);
if(guess == 0) {
return mid;
} else if(guess == -1) {
right = mid-1;
} else {
left = mid+1;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(new GuessNumberHigherLower(10).guessNumber(10));
}
}
import java.util.Random;
public class GuessGame {
int pick=-1;
public void init(int n) {
Random random = new Random(1);
pick = random.nextInt(n);
System.out.println("Random Pick : "+pick);
}
protected int guess(int guess) {
if(guess == pick) {
return 0;
} else if(guess >pick) {
return -1;
} else {
return 1;
}
}
}
Complexity Analysis:
Time complexity: Above code runs in O(log n) time where n is the length of input array nums.
Space complexity: O(1).
Above implementations source code can be found at
GitHub link for Java code