Guess Number Higher or Lower - Solution & Explanation
Problem Statement
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
-1: Your guess is higher than the number I picked (i.e.num > pick).1: Your guess is lower than the number I picked (i.e.num < pick).0: your guess is equal to the number I picked (i.e.num == pick).
Return the number that I picked.
Example 1:
Input: n = 10, pick = 6 Output: 6
Example 2:
Input: n = 1, pick = 1 Output: 1
Example 3:
Input: n = 2, pick = 1 Output: 1
Constraints:
1 <= n <= 231 - 11 <= pick <= n
Approach Overview
Problem Overview: You need to guess a hidden number between 1 and n. An API guess(num) tells whether your guess is correct, too high, or too low. The goal is to minimize guesses while identifying the exact number.
Approach 1: Iterative Method with Linear Search (O(n) time, O(1) space)
The simplest strategy is to start from 1 and repeatedly call guess(i) while incrementing the value. If the API returns 0, you found the hidden number. If it returns -1, your guess is too high and you stop. This approach works because the range is sequential, but it may require checking every number up to n. The time complexity is O(n) since each value may be tested once, while space usage stays O(1). It demonstrates the basic interaction pattern but becomes inefficient for large ranges.
Approach 2: Binary Search Method (O(log n) time, O(1) space)
The efficient solution applies binary search on the range [1, n]. Start with two pointers: left = 1 and right = n. Compute the middle value and call guess(mid). If the result is 0, the number is found. If the API returns -1, the guess is too high so move the right boundary to mid - 1. If it returns 1, the guess is too low so move the left boundary to mid + 1. Each step halves the search range, which reduces the number of API calls dramatically. The algorithm runs in O(log n) time with constant O(1) extra space.
This problem is also categorized as an interactive problem because your program must repeatedly query an external API instead of accessing the hidden value directly. The key insight is recognizing that the API response gives ordering information, which allows binary search to eliminate half the possibilities each step.
Recommended for interviews: Binary search is the expected solution. Interviewers want to see you recognize that the API feedback provides a sorted decision boundary, enabling a classic binary search pattern. Mentioning the linear scan first shows understanding of the brute-force baseline, but implementing the O(log n) binary search demonstrates strong problem-solving and algorithm knowledge.
Approach 1: Binary Search Method
This approach uses binary search to guess the number. We maintain two pointers, low and high, representing the current range of numbers we need to search. Then, we guess the middle number of the range and adjust our range based on the response from the guess API. If the guessed number is correct, we return it. Otherwise, we adjust the low or high pointers and repeat the process until the number is guessed correctly.
The code uses a binary search to find the number picked. The guess function simulates the API call that returns whether the guessed number is too high, too low, or correct.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Iterative Method with Linear Search
This approach is a straightforward linear search that iterates from 1 to n guessing each number one by one until it finds the correct pick. It's simple but not efficient for larger values of n and is provided here primarily for educational purposes.
This C code implements a linear search. It simply checks each number in sequence until it finds the correct one using the guess API.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Binary Search
We perform a binary search in the interval [1,..n], and find the first number that satisfies guess(x) <= 0, which is the answer.
The time complexity is O(log n), where n is the upper limit given in the problem. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search Method | Time Complexity: O(log n) |
| Iterative Method with Linear Search | Time Complexity: O(n) |
| Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Linear Search | O(n) | O(1) | Useful as a baseline or when the search range is very small |
| Binary Search | O(log n) | O(1) | Best choice when the range is ordered and the API reveals higher/lower hints |
Video Solution
Guess Number Higher or Lower - Leetcode 374 - Python • NeetCode • 47,735 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Guess Number Higher or Lower easy or hard?
Guess Number Higher or Lower Python Java solution
How to solve Guess Number Higher or Lower in O(log n)?
What is the best approach for Guess Number Higher or Lower?
Is Guess Number Higher or Lower asked at Google Amazon Meta?
What data structure is used in Guess Number Higher or Lower?
What is the time complexity of Guess Number Higher or Lower?
Ready to solve this problem?
Practice Guess Number Higher or Lower with our built-in code editor and test cases.
Practice on FleetCode