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.
# @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

Tanishq Chaudhary

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