Guess Number Higher or Lower — InterviewPrepKit

Problem

We play a guessing game. I pick a secret number between 1 and n (inclusive). You repeatedly guess a number, and I answer through a pre-defined API:

guess(num) returns -1 if my secret number is lower than your guess,
returns 1 if my secret number is higher than your guess,
returns 0 if you guessed it.

Given n, return the secret number using as few calls to guess as possible.

Examples

Input: n = 10, secret pick = 6 → Output: 6 (Guess 5 → answer 1 (higher); guess 8 → answer -1 (lower); guess 6 → answer 0.)
Input: n = 1, secret pick = 1 → Output: 1 (Only one possible number; the first guess must be it.)
Input: n = 2, secret pick = 1 → Output: 1 (Guess 1 → answer 0 immediately.)

Constraints

1 <= n <= 2^31 - 1
1 <= pick <= n
n can be huge, so the number of guesses must be logarithmic, not linear.

Think about it first

Hint 1

Each `guess` answer tells you which side of your guess the secret lies on, not just whether you were right. What can you discard once you know that?

Hint 2

This is searching a sorted range `[1..n]` for an unknown value, where the comparison is the API call. What algorithm finds a value in a sorted range with O(log n) comparisons?

Hint 3

Maintain `lo = 1`, `hi = n`. Guess the midpoint: if the API says -1, the secret is below, so `hi = mid - 1`; if 1, `lo = mid + 1`; if 0, return `mid`. Since the pick is guaranteed to exist, the loop always terminates with an answer.

TL;DR

Binary search over [1, n] using the guess API as the comparator — O(log n) time, O(1) space.

Approach 1 — Brute force (guess every number)

Try 1, then 2, then 3, … until the API answers 0.

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

def guessNumber(n: int) -> int:
    for num in range(1, n + 1):
        if guess(num) == 0:
            return num
    return n  # unreachable: the pick is guaranteed to exist

Time O(n) API calls, space O(1). With n up to 2^31 - 1 ≈ 2.1 billion, a worst-case pick near n means billions of calls, which is infeasible.

Approach 2 — Binary search on the range

The API’s three-way answer is the comparison binary search needs. The candidates 1..n form a sorted range, and each call to guess(mid) tells us whether the secret is below, above, or at mid, so every call halves the remaining range.

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

def guessNumber(n: int) -> int:
    lo, hi = 1, n
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        verdict = guess(mid)
        if verdict == 0:
            return mid
        if verdict == -1:      # secret is lower
            hi = mid - 1
        else:                  # secret is higher
            lo = mid + 1
    return -1  # unreachable: the pick always exists in [1, n]

Walkthrough on n = 10, secret pick = 6:

lo=1, hi=10 → mid=5, guess(5)=1 (secret higher) → lo=6.
lo=6, hi=10 → mid=8, guess(8)=-1 (secret lower) → hi=7.
lo=6, hi=7 → mid=6, guess(6)=0 → return 6.

Three calls instead of six. Time O(log n), about 31 calls even at n = 2^31 - 1. Space O(1).

Approach 3 — Recursive binary search

The same halving can be written recursively: guess the middle of the current range, then recurse into the half the API points to. This is the divide-and-conquer phrasing of the same algorithm.

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

def guessNumber(n: int) -> int:
    def go(lo: int, hi: int) -> int:
        mid = lo + (hi - lo) // 2
        verdict = guess(mid)
        if verdict == 0:
            return mid
        if verdict == -1:
            return go(lo, mid - 1)
        return go(mid + 1, hi)

    return go(1, n)

Walkthrough on n = 2, secret pick = 1:

go(1, 2): mid=1, guess(1)=0 → return 1.

Time O(log n), space O(log n) for the recursion stack. Same call count as the iterative version, slightly worse space. Be ready to write either formulation.

Common pitfalls

Reversing the API’s meaning: -1 means your guess is too high (secret is lower), not “go higher”. Misreading it sends the search the wrong way, and the loop exits without finding the pick.
In fixed-width-integer languages, (lo + hi) / 2 overflows when hi is near 2^31 - 1, which this problem’s bounds are set up to expose. Write lo + (hi - lo) // 2.
Shrinking to hi = mid / lo = mid instead of stepping past mid causes an infinite loop on a two-value range.
Starting the range at 0: the secret is in [1, n], so a guess on 0 wastes a call and can loop when n = 1.

Pattern takeaway

Binary search does not need an array. It needs an ordered range of candidates and an oracle that reports too low, too high, or found. Any time an API, a predicate, or a computation gives that three-way (or two-way) verdict over a monotone range, you can halve the range to the answer in logarithmic steps.