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 <= nThe key idea in #374 Guess Number Higher or Lower is to efficiently determine a hidden number within a given range using feedback from an API such as guess(num). This function tells you whether the picked number is higher, lower, or equal to your guess. Instead of checking every number sequentially, the optimal strategy is to apply Binary Search.
Binary search works well because the search space is sorted and bounded between 1 and n. Start by guessing the middle value of the range. Based on the API’s response, eliminate half of the remaining possibilities—either the lower half or the upper half. Continue narrowing the range until the correct number is found.
This divide-and-conquer approach dramatically reduces the number of guesses needed. Each step halves the search space, leading to a logarithmic number of operations. The algorithm only stores a few boundary variables, making it very space efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search | O(log n) | O(1) |
NeetCode
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.
Time Complexity: O(log n)
Space Complexity: O(1)
1#include<stdio.h>
2
3int guess(int num);
4
5int guessNumber(int n) {
6 int low =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.
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.
Time Complexity: O(n)
Space Complexity: O(1)
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews at major tech companies. It tests a candidate’s understanding of binary search, boundary handling, and efficient search strategies.
No special data structure is required for this problem. The algorithm simply maintains two boundary pointers representing the current search range and applies binary search logic.
The optimal approach is Binary Search. Since the range of possible numbers is ordered, you can repeatedly guess the middle value and use the API feedback to discard half of the search space each time. This reduces the number of guesses to logarithmic time.
Binary search is ideal because the possible answers lie within a sorted numeric range from 1 to n. Each response from the guess API tells you which half of the range to explore next, allowing the search space to shrink quickly.
The JavaScript solution uses a straightforward loop to incrementally try each number from 1 up to n until the picked number is found.