0300 - 0399
0374 - Guess Number Higher or Lower (Easy)
Problem Link
https://leetcode.com/problems/guess-number-higher-or-lower/
Problem Statement
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: 6Example 2:
Input: n = 1, pick = 1
Output: 1Example 3:
Input: n = 2, pick = 1
Output: 1Constraints:
1 <= n <= 2^31 - 11 <= pick <= n
Approach 1: Binary Search
See Binary Search for basic understanding.
/**
* 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);
*/
class Solution {
public:
int guessNumber(int n) {
int l = 1, r = n;
while (l < r) {
// middle point
int m = l + (r - l) / 2;
// check the result
int x = guess(m);
// found the answer
if (x == 0) return m;
// exclude m
else if (x == 1) l = m + 1;
// include m
else r = m;
}
return l;
}
};impl Solution {
unsafe fn guessNumber(n: i32) -> i32 {
let mut l = 1;
let mut r = n;
while l < r {
let m = l + (r - l) / 2;
let x = guess(m);
if x == 1 {
l = m + 1;
} else {
r = m;
}
}
l
}
}impl Solution {
unsafe fn guessNumber(n: i32) -> i32 {
let mut l = 1;
let mut r = n;
loop {
let m = l + (r - l) / 2;
match guess(m) {
-1 => r = m - 1,
1 => l = m + 1,
_ => return m
};
}
}
}# 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:
class Solution:
def guessNumber(self, n: int) -> int:
left = 1
right = n
while left <= right:
mid = (left + right) // 2
if guess(mid) == 1:
left = mid + 1
elif guess(mid) == -1:
right = mid
else:
return mid/**
* Forward declaration of guess API.
* @param {number} 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
* var guess = function(num) {}
*/
/**
* @param {number} n
* @return {number}
*/
var guessNumber = function (n) {
let left = 1;
let right = n;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (guess(mid) === 1) {
left = mid + 1;
} else if (guess(mid) === -1) {
right = mid;
} else {
return mid;
}
}
};