Guess Number Higher or Lower solution and explanation
Google
9 more videos on this problem
Guess Number Higher or Lower - Leetcode 374 - PythonNeetCode · 6:04 · 47K views
Leetcode | 374. Guess Number Higher or Lower | Easy | Java SolutionDeveloper Docs · 3:39 · 4K views
Guess Number Higher or Lower #leetcode #leetcode75Deepti Talesra · 5:56 · 1K views
Guess Number Higher or Lower | LeetCode 374 | Coder CampCoders Camp · 7:22 · 933 views
Guess Number Higher or Lower - LeetCode 374 - JavaScriptAlgoJS · 4:12 · 885 views
Guess Number Higher or Lower | Решение на Python | LeetCode 374Сурен Хоренян · 5:32 · 597 views
LeetCode 374 : Guess Number Higher or Lower || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 8:22 · 478 views
Daily Leetcode #960: Nov 16, 2022 - 374. Guess Number Higher or LowerProgramming Live with Larry · 5:17 · 443 views
#Leetcode 374. Guess Number Higher or Lower |#JavaScript faster than 99%Leetcode JavaScript · 5:12 · 324 views
Daily Leetcode #560: Oct 12, 2021 - 374. Guess Number Higher or LowerProgramming Live with Larry · 5:02 · 224 views
The problem
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.
def guessNumber(n):
low, high = 1, n
while low <= high:
mid = (low + high) // 2
res = guess(mid)
if res == 0:
return mid
elif res < 0:
high = mid - 1
else:
low = mid + 1
return -1 # should not reach herepublic class Solution {
public int guessNumber(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1; // should not reach here
}
}class Solution {
public:
int guessNumber(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1; // should not reach here
}
};var guessNumber = function(n) {
let low = 1, high = n;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
let res = guess(mid);
if (res === 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1; // should not reach here
};#include<stdio.h>
int guess(int num);
int guessNumber(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1; // should not reach here
}public class Solution {
public int GuessNumber(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1; // should not reach here
}
}This Python function uses binary search to find the target number. It calls the guess API to check if the guessed number is correct or needs adjustment.
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.
def guessNumber(n):
for i in range(1, n + 1):
if guess(i) == 0:
return i
return -1 # should not reach herepublic class Solution {
public int guessNumber(int n) {
for (int i = 1; i <= n; i++) {
if (guess(i) == 0) {
return i;
}
}
return -1; // should not reach here
}
}class Solution {
public:
int guessNumber(int n) {
for (int i = 1; i <= n; i++) {
if (guess(i) == 0) {
return i;
}
}
return -1; // should not reach here
}
};var guessNumber = function(n) {
for (let i = 1; i <= n; i++) {
if (guess(i) === 0) {
return i;
}
}
return -1; // should not reach here
};#include<stdio.h>
int guess(int num);
int guessNumber(int n) {
for (int i = 1; i <= n; i++) {
if (guess(i) == 0) {
return i;
}
}
return -1; // should not reach here
}public class Solution {
public int GuessNumber(int n) {
for (int i = 1; i <= n; i++) {
if (guess(i) == 0) {
return i;
}
}
return -1; // should not reach here
}
}This Python function applies linear search, testing each integer from 1 through n until the correct number is found.
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).
/**
* Forward declaration of guess API.
* @param {number} num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* var guess = function(num) {}
*/
function guessNumber(n: number): number {
let l = 1;
let r = n;
while (l < r) {
const mid = (l + r) >>> 1;
if (guess(mid) <= 0) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is higher than the picked number
* 1 if num is lower than the picked number
* otherwise return 0
* func guess(num int) int;
*/
func guessNumber(n int) int {
return sort.Search(n, func(i int) bool {
i++
return guess(i) <= 0
}) + 1
}/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* unsafe fn guess(num: i32) -> i32 {}
*/
impl Solution {
unsafe fn guessNumber(n: i32) -> i32 {
let mut l = 1;
let mut r = n;
loop {
let mid = l + (r - l) / 2;
match guess(mid) {
-1 => {
r = mid - 1;
}
1 => {
l = mid + 1;
}
_ => {
break mid;
}
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Method | Time Complexity: O(log n) |
| Iterative Method with Linear Search | Time Complexity: O(n) |
| Binary Search | – |
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 |
Frequently asked questions
Is Guess Number Higher or Lower easy or hard?
Guess Number Higher or Lower is considered an Easy problem on LeetCode. The main concept is recognizing that the guess API provides ordering information, making binary search the correct approach.
Guess Number Higher or Lower Python Java solution
The same binary search logic works across languages such as Python, Java, C++, C#, C, and JavaScript. Maintain left and right bounds, compute the midpoint, and adjust the range based on the guess API response until the correct value is returned.
How to solve Guess Number Higher or Lower in O(log n)?
Use binary search on the range from 1 to n. Compute the midpoint and call the guess API. If the result indicates the guess is too high, move the right boundary left. If it is too low, move the left boundary right. Continue until the API returns 0.
What is the best approach for Guess Number Higher or Lower?
Binary search is the best approach because each guess eliminates half of the remaining search range. By adjusting the left and right boundaries based on the API response, the hidden number can be found in O(log n) time with O(1) space.
Is Guess Number Higher or Lower asked at Google Amazon Meta?
This problem represents a classic binary search pattern that frequently appears in technical interviews at companies like Google, Amazon, and Meta. It tests whether candidates can recognize ordered search spaces and reduce them efficiently.
What data structure is used in Guess Number Higher or Lower?
The solution does not rely on a complex data structure. It mainly uses the binary search algorithm with two integer pointers representing the current search range.
What is the time complexity of Guess Number Higher or Lower?
The optimal binary search solution runs in O(log n) time since the search interval is halved after each guess. A naive linear search approach would require up to O(n) guesses in the worst case.