LeetCode 374: Guess Number Higher or Lower

Problem Restatement

We are playing a number guessing game.

A hidden number pick has been chosen from:

1 to n

We need to find pick.

We cannot read pick directly. Instead, we call a provided API:

guess(num)

The API returns:

Return the hidden number. The search range is 1 <= pick <= n, and n can be as large as 2^31 - 1.

Input and Output

Example function shape:

def guessNumber(n: int) -> int:
    ...

Examples

Example 1:

n = 10
pick = 6

If we guess 5, the API returns 1, because 5 is too low.

If we guess 8, the API returns -1, because 8 is too high.

If we guess 6, the API returns 0.

So the answer is:

6

Example 2:

n = 1
pick = 1

There is only one possible number, so the answer is:

1

First Thought: Linear Search

A simple solution is to try every number from 1 to n.

class Solution:
    def guessNumber(self, n: int) -> int:
        for num in range(1, n + 1):
            if guess(num) == 0:
                return num

This is correct, but it can take O(n) calls to guess.

Since n may be very large, this is too slow.

Key Insight

The API tells us which half of the search range can be discarded.

If we guess mid:

This is exactly binary search.

Algorithm

Maintain a search range:

left = 1
right = n

While left <= right:

1. Compute the middle value.
2. Call guess(mid).
3. If the result is 0, return mid.
4. If the result is -1, move right to mid - 1.
5. If the result is 1, move left to mid + 1.

Correctness

The hidden number starts inside the range [1, n].

At each step, the algorithm guesses mid.

If guess(mid) == 0, then mid equals the hidden number, so returning it is correct.

If guess(mid) == -1, then mid is greater than the hidden number. Every number greater than or equal to mid can be discarded, so the hidden number remains in [left, mid - 1].

If guess(mid) == 1, then mid is smaller than the hidden number. Every number less than or equal to mid can be discarded, so the hidden number remains in [mid + 1, right].

Thus the search range always contains the hidden number until it is found. Since the range shrinks every iteration, the algorithm eventually returns the correct number.

Complexity

Implementation

# The guess API is already defined for you.
# def guess(num: int) -> int:
#     ...

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n

        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)

            if result == 0:
                return mid

            if result == -1:
                right = mid - 1
            else:
                left = mid + 1

        return -1

Code Explanation

The search starts with the full range:

left = 1
right = n

The midpoint is computed safely:

mid = left + (right - left) // 2

In Python, overflow is not an issue. In fixed-width integer languages, this form avoids overflow.

Then we call the API:

result = guess(mid)

If the result is 0, we found the answer.

If the result is -1, our guess is too high:

right = mid - 1

If the result is 1, our guess is too low:

left = mid + 1

The final return -1 is only a safety fallback. Under the problem constraints, the answer always exists.

Testing

LeetCode provides the guess API. For local testing, we can mock it with a closure.

def make_solution(pick):
    def guess(num):
        if num > pick:
            return -1
        if num < pick:
            return 1
        return 0

    class Solution:
        def guessNumber(self, n: int) -> int:
            left = 1
            right = n

            while left <= right:
                mid = left + (right - left) // 2
                result = guess(mid)

                if result == 0:
                    return mid

                if result == -1:
                    right = mid - 1
                else:
                    left = mid + 1

            return -1

    return Solution()

def run_tests():
    assert make_solution(6).guessNumber(10) == 6
    assert make_solution(1).guessNumber(1) == 1
    assert make_solution(1).guessNumber(2) == 1
    assert make_solution(2).guessNumber(2) == 2
    assert make_solution(1702766719).guessNumber(2126753390) == 1702766719

    print("all tests passed")

run_tests()

Test meaning: