< Back





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.