Guess Number Higher or Lower — InterviewPrepKit

Solving tips

Recognize binary search where the guess API is the comparator over the sorted range [1, n]; each three-way answer halves the candidates.
Read the API carefully: guess returns -1 when your guess is too high (secret is lower, so hi = mid-1) and 1 when the secret is higher (lo = mid+1).
Use mid = lo + (hi-lo)//2 to avoid overflow, since n can reach 2^31-1 and that is exactly what the bounds punish.
O(log n) API calls, O(1) space; step past mid (not lo = mid / hi = mid) to avoid an infinite loop on a two-value range.

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 answer from `guess` is more than a yes/no — it tells you which *side* of your guess the secret lies on. What does that let you discard?

Hint 2

This is exactly 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:

class Solution:
    def guessNumber(self, 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 — hopeless.

Approach 2 — Binary search on the range

The insight: the API’s three-way answer is exactly 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. Binary search is the classical algorithm that repeatedly halves a monotone search space with one comparison per step.

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

class Solution:
    def guessNumber(self, 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 insight: the same halving reads naturally as “guess the middle of the current range, then recurse into the half the API points to” — the divide-and-conquer phrasing of the identical algorithm.

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

class Solution:
    def guessNumber(self, 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) recursion stack — same call count as the iterative version, slightly worse space; know both formulations.

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 — this problem’s bounds are chosen to punish exactly that. Write lo + (hi - lo) // 2.
Shrinking to hi = mid / lo = mid instead of stepping past mid — infinite loop on a two-value range.
Starting the range at 0: the secret is in [1, n], and wasting a guess on 0 both misreads the problem and can loop when n = 1.

Pattern takeaway

Binary search doesn’t need an array — it needs an ordered range of candidates and an oracle that says “too low / too high / found”. Any time an API, a predicate, or a computation gives you that three-way (or even two-way) verdict over a monotone range, you can halve your way to the answer in logarithmic steps.