Skip to content

374. Guess Number Higher Or Lower

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Brute Force Start from 1, incrementally guess each number up to n until the correct number is found \(O(n)\) \(O(1)\)
Binary Search Repeatedly guess the middle of the current range and narrow the range based on feedback from the guess API \(O(\log n)\) \(O(1)\)

Implementation

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:
class Solution:
    def guessNumber(self, n: int) -> int:
        l = 1
        r = n

        while True:
            m = (l + r) // 2

            res = guess(m)
            if res == -1:
                r = m - 1
            elif res == 1:
                l = m + 1
            else:
                return m