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 <= nThis 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(1)
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Binary Search Method | Time Complexity: O(log n) |
| Iterative Method with Linear Search | Time Complexity: O(n) |
Guess Number Higher or Lower - Leetcode 374 - Python • NeetCode • 38,554 views views
Watch 9 more video solutions →Practice Guess Number Higher or Lower with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor