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
• `0` if `num` is the correct guess
• -1 if `num` is lower than actual value
• 1 if `num` is higher than actual value

Observation

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[i]` where `a` is the array we are searching in.

Binary Search

A quick review on binary search

Have `l` and `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 `m` with `a[i]`, but in this question, Guess Number, we can instead do `x = guess(m)`.

• if `x == 0` return `m` right away
• if `x > 0` we have `m`, the mid, too small. We increase the `l = m + 1`, to mark that the array is in the second half
• if `x < 0` we have `m` too big, so we reduce the `r = m - 1` so that in the next iteration, `(l + r)//2` gives a smaller `m`

Guess Number Code

```# The guess API is already defined for you.
# @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
```
Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

Recommended Posts

Gas Station | InterviewBit | Solution Explained

June 13, 2022

Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.