Guess Number Higher or Lower | LeetCode | Solution Explained
374. Guess Number Higher or Lower LeetCode is based on the understanding of binary search, and how we can integrate the API provided with binary search. Problem Link.
Guess Number: Problem Discussion
- input: n
- from the range of [1, n], the problem picks a number
- using the API
guess(num)we can get it to return a
numis the correct guess
- -1 if
numis lower than actual value
- 1 if
numis higher than actual value
The key point is to realize the similarity of Guess Number structure with binary search. Binary search uses the same logic, but instead of using the
guess(num) API, we commonly use the
a is the array we are searching in.
A quick review on binary search
r demarcating the ranges of the array (in this case its implicit – from the range [1,n]) we are trying to search in.
We then find the
m = (l+r)//2
Be careful to consider overflow – use
m = l + (r-l)//2 to get the same result in Java/C/C++.
At this point, we usually compare
a[i], but in this question, Guess Number, we can instead do
x = guess(m).
x == 0return
x > 0we have
m, the mid, too small. We increase the
l = m + 1, to mark that the array is in the second half
x < 0we have
mtoo big, so we reduce the
r = m - 1so that in the next iteration,
(l + r)//2gives a smaller
Guess Number Code
# 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: class Solution: def guessNumber(self, n: int) -> int: l, r = 1, n while l < r: m = (l+r)//2 x = guess(m) if x == 0: return m elif x > 0: l = m + 1 else: r = m - 1 return l
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022