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 value	Meaning
`-1`	Our guess is too high, so `num > pick`
`1`	Our guess is too low, so `num < pick`
`0`	Our guess is correct, so `num == pick`

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

Input and Output

Item	Meaning
Input	Integer `n`
Hidden value	`pick`, chosen from `1` to `n`
Output	The value of `pick`
API	`guess(num)` tells whether the guess is high, low, or correct

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:

Example 2:

n = 1
pick = 1

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

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:

API result	What we know	Next range
`0`	`mid` is the answer	Stop
`-1`	`mid` is too high	Search left half
`1`	`mid` is too low	Search right half

This is exactly binary search.

Algorithm

Maintain a search range:

left = 1
right = n

While left <= right:

Compute the middle value.
Call guess(mid).
If the result is 0, return mid.
If the result is -1, move right to mid - 1.
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

Metric	Value	Why
Time	`O(log n)`	Each guess halves the search range
Space	`O(1)`	Only a few variables are stored

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:

Test	Why
`n = 10, pick = 6`	Standard example
`n = 1, pick = 1`	Smallest range
`pick` at left boundary	Checks left-side shrinking
`pick` at right boundary	Checks right-side shrinking
Large values	Confirms logarithmic search and safe midpoint