Guess Number Higher or Lower
Understanding the Problem
We need to find a secret number in the range [1, n] using only the guess API. Each call to guess(num) tells us one of three things: our guess is correct (returns 0), too high (returns -1), or too low (returns 1).
This is a search problem. We're looking for a specific value in a sorted range, and the guess API is a comparison oracle that tells us which direction to go. The range [1, n] is already sorted, so binary search applies directly.
The constraint that matters is the size of n: up to 2^31 - 1 (about 2.1 billion). Checking every number one by one could take 2.1 billion API calls. Since the search space is sorted, each guess can eliminate half the remaining candidates instead of just one, which is what binary search does.
Key Constraints:
1 <= n <= 2^31 - 1→ n can be up to about 2.1 billion, which rules out a linear scan. With binary search, log2(2^31) = 31, so we need at most 31 guesses. This bound also means the midpoint formula must avoid integer overflow, sincelow + highcan exceed the 32-bit signed range when both are near 2^31.1 <= pick <= n→ The answer always exists within the range, so there is no "not found" case to handle.
Approach 1: Linear Scan
Intuition
Try every number from 1 to n until the API confirms a match. This ignores the higher/lower feedback entirely, but it is guaranteed to find the answer since pick is somewhere in [1, n]. Start at 1, call guess(1), then guess(2), and continue until the call returns 0.
Algorithm
- Start from number 1.
- Call
guess(i)for each numberifrom 1 to n. - If
guess(i)returns 0, returnias the answer.
Example Walkthrough
Input: n = 10, pick = 6
We call guess(1), guess(2), ..., guess(6). On the sixth call, guess(6) returns 0 and we return 6. We made 6 API calls to find the answer.
Code
- Time Complexity: O(n). In the worst case, the picked number is n, and we try every number from 1 to n before finding it. Each guess is O(1), so the total is O(n).
- Space Complexity: O(1). We only use a single loop variable. No extra data structures needed.
The linear scan throws away the higher/lower feedback. Using that feedback to discard half the remaining range on every guess is what the next approach does.
Approach 2: Binary Search
Intuition
We have a sorted range [1, n], and the guess API acts as a comparator that tells us whether the pick is in the left half or the right half of our current range. Guessing the midpoint and discarding the half that cannot contain the pick reduces the candidate count from m to m/2 in a single call.
Concretely, on the range [1, 100], a guess of 50 that returns "higher" rules out 1 through 50 in one step, leaving [51, 100]. The next guess is 75, the midpoint of that smaller range. With n up to 2^31 - 1, this reaches the answer in at most 31 guesses instead of up to 2 billion.
The invariant is that the pick, if it exists, always lies within [low, high]. It holds initially because the pick is in [1, n]. Each step preserves it: when guess(mid) returns -1 the pick is strictly less than mid, so excluding mid and everything above it (high = mid - 1) cannot drop the pick; the symmetric argument covers the "higher" case. Since mid always lies in [low, high] and at least one endpoint moves past it each iteration, the range strictly shrinks, so the loop terminates.
After k guesses the range holds at most n / 2^k values. Solving n / 2^k = 1 gives k = log2(n), which is why the algorithm runs in O(log n). For n = 2^31, that is at most 31 iterations.
Algorithm
- Set
low = 1andhigh = n. - While
lowis less than or equal tohigh: - Compute the midpoint:
mid = low + (high - low) / 2. - Call
guess(mid). - If the result is 0, return
mid(we found the number). - If the result is -1, the pick is lower, so set
high = mid - 1. - If the result is 1, the pick is higher, so set
low = mid + 1. - Return -1 (should never reach here since the pick is guaranteed to exist).
Example Walkthrough
Code
- Time Complexity: O(log n). Each iteration halves the search space. Starting from n elements, we reach 1 element after at most log2(n) iterations. For n = 2^31 - 1, that's at most 31 iterations.
- Space Complexity: O(1). We only use three integer variables:
low,high, andmid. No recursion, no extra data structures.