374

374. Guess Number Higher or Lower

We’re playing a guessing game, someone picks a number and we have to guess it. They tell us whether we’ve guessed the number using the guess() API, or receive a 1 or -1 response if the number is higher or lower, respectively. We use binary search to guess the number.

The solution is as follows:

class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 1, n
 
        while l <= r:
            m = (r + l) // 2
            res = guess(m)
 
            if not res:
                return m
            elif res > 0:
                l = m + 1
            else:
                r = m - 1

_ Time Complexity:

O(log(n)) - We use binary search to find the number.

_ Space Complexity:

O(1) - We use constant space to retain our variables.