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.
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
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516
# The guess API is already defined for you.# @param num, your guess# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0# def guess(num: int) -> int:classSolution:defguessNumber(self,n:int)->int:left,right=1,nwhileleft<right:mid=(left+right)>>1ifguess(mid)<=0:right=midelse:left=mid+1returnleft
1 2 3 4 5 6 7 8 91011121314151617181920212223
/** * 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); */publicclassSolutionextendsGuessGame{publicintguessNumber(intn){intleft=1,right=n;while(left<right){intmid=(left+right)>>>1;if(guess(mid)<=0){right=mid;}else{left=mid+1;}}returnleft;}}
1 2 3 4 5 6 7 8 9101112131415161718192021222324
/** * 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); */classSolution{public:intguessNumber(intn){intleft=1,right=n;while(left<right){intmid=left+((right-left)>>1);if(guess(mid)<=0){right=mid;}else{left=mid+1;}}returnleft;}};
1 2 3 4 5 6 7 8 9101112131415161718192021
/** * 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 * func guess(num int) int; */funcguessNumber(nint)int{left,right:=1,nforleft<right{mid:=(left+right)>>1ifguess(mid)<=0{right=mid}else{left=mid+1}}returnleft}
1 2 3 4 5 6 7 8 910111213141516171819202122
/** * Forward declaration of guess API. * @param {number} 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 * var guess = function(num) {} */functionguessNumber(n:number):number{letl=1;letr=n;while(l<r){constmid=(l+r)>>>1;if(guess(mid)<=0){r=mid;}else{l=mid+1;}}returnl;}
/** * 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 * unsafe fn guess(num: i32) -> i32 {} */implSolution{unsafefnguessNumber(n:i32)->i32{letmutl=1;letmutr=n;loop{letmid=l+(r-l)/2;matchguess(mid){-1=>{r=mid-1;}1=>{l=mid+1;}_=>{breakmid;}}}}}
1 2 3 4 5 6 7 8 91011121314151617181920212223
/** * 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); */publicclassSolution:GuessGame{publicintGuessNumber(intn){intleft=1,right=n;while(left<right){intmid=left+((right-left)>>1);if(guess(mid)<=0){right=mid;}else{left=mid+1;}}returnleft;}}
Solution 2
1 2 3 4 5 6 7 8 91011
# The guess API is already defined for you.# @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# def guess(num: int) -> int:classSolution:defguessNumber(self,n:int)->int:returnbisect.bisect(range(1,n+1),0,key=lambdax:-guess(x))
1 2 3 4 5 6 7 8 9101112131415
/** * 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 * func guess(num int) int; */funcguessNumber(nint)int{returnsort.Search(n,func(iint)bool{i++returnguess(i)<=0})+1}