374. Guess Number Higher or Lower
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 3 possible results:
-1
: The number I picked is lower than your guess (i.e.pick < num
).1
: The number I picked is higher than your guess (i.e.pick > num
).0
: The number I picked is equal to your guess (i.e.pick == num
).
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
Example 4:
Input: n = 2, pick = 2 Output: 2
Constraints:
1 <= n <= 231 - 1
1 <= pick <= n
Solution To the Above Question
This question is similar to the binary search and if you know binary search then you can easily solve this.
Just read the binary search algo once and then you can easily solve this.
Just read the binary search algo once and then you can easily solve this.
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int start=1;
int end=n;
while(start<=end){
int mid=start + (end-start)/2;
int ans=guess(mid);
if(ans==0){
return (mid);
}
else if(ans==1){
start=mid+1;
}
else{
end=mid-1;
}
}
return 0;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.