Skip to main content
CodePeetCodePeet
CodePeet 250

Guess Number Higher or Lower

EASYProblemSolveExternal Links

Description

We are playing the Guess Game. The game works as follows:

I pick a number from 1 to n. You have to guess which number I picked. The picked number remains the same throughout the game.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You are given 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.

Examples

Example 1

Input: n = 10, pick = 6

Output: 6

Explanation: We need to find the picked number 6 out of the range [1, 10]. Using the guess API, we can determine whether our guess is too high, too low, or correct, and converge on the answer.

Example 2

Input: n = 1, pick = 1

Output: 1

Explanation: There is only one number in the range [1, 1]. The only possible pick is 1, so we return 1.

Example 3

Input: n = 2, pick = 1

Output: 1

Explanation: The range is [1, 2]. We guess 1, and guess(1) returns 0, meaning we guessed correctly. Return 1.

Constraints

  • 1 ≤ n ≤ 2^31 - 1
  • 1 ≤ pick ≤ n

Editorial

Brute Force

Intuition

The simplest approach is to guess every number starting from 1, one by one, until we find the correct answer.

Try 1, then 2, then 3, ... until guess(i) returns 0.

Since the picked number is guaranteed to be in the range [1, n], this linear scan is guaranteed to find it eventually. We just call the guess API for each number sequentially and return the first one that matches.

This approach doesn't use any clever strategy — it's equivalent to asking "Is it 1? Is it 2? Is it 3?" and so on. It's the most natural way a beginner would think about the problem.

Step-by-Step

Let's trace through n = 10, pick = 6 using the brute force approach:

Step 1: Guess 1. Call guess(1). Returns 1 (too low). The picked number is higher than 1.

Step 2: Guess 2. Call guess(2). Returns 1 (too low). The picked number is higher than 2.

Step 3: Guess 3. Call guess(3). Returns 1 (too low). The picked number is higher than 3.

Step 4: Guess 4. Call guess(4). Returns 1 (too low). The picked number is higher than 4.

Step 5: Guess 5. Call guess(5). Returns 1 (too low). The picked number is higher than 5.

Step 6: Guess 6. Call guess(6). Returns 0 (correct!). We found the picked number. Return 6.

Algorithm

  1. Iterate i from 1 to n.
  2. For each i, call guess(i).
  3. If guess(i) returns 0, return i — we found the picked number.
  4. Otherwise, continue to the next number.

Code

// 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
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        for (int i = 1; i <= n; i++) {
            if (guess(i) == 0) {
                return i;
            }
        }
        return n; // This line is never reached
    }
};
# The guess API is already defined for you.
# @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
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        for i in range(1, n + 1):
            if guess(i) == 0:
                return i
        return n  # This line is never reached
/* The guess API is defined in the parent class GuessGame.
   @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
   int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        for (int i = 1; i <= n; i++) {
            if (guess(i) == 0) {
                return i;
            }
        }
        return n; // This line is never reached
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, the picked number is n itself, and we must guess every number from 1 to n before finding it. This requires n calls to the guess API.

Space Complexity: O(1)

We only use a single loop variable i. No additional data structures are allocated.

Why This Approach Is Not Efficient

The brute force approach guesses numbers sequentially: 1, 2, 3, 4, 5, ... Each guess eliminates only one candidate. If the picked number is near the end of the range, we waste almost all of our guesses on wrong answers.

But notice something crucial: the guess API doesn't just tell us "wrong" — it tells us which direction to go. When guess(num) returns 1 (too low), it means the answer is somewhere in [num + 1, n]. When it returns -1 (too high), the answer is in [1, num - 1].

This directional feedback is exactly what makes Binary Search applicable:

Instead of guessing 1, 2, 3, 4, ..., guess the middle of the current range. The API response tells us which half to keep, eliminating half the candidates in one step.

For n = 2,147,483,647 (the maximum constraint):

  • Linear scan: up to ~2.1 billion guesses
  • Binary search: at most 31 guesses (log₂(2^31) = 31)

This is the difference between an approach that could time out and one that runs almost instantly.

Optimal Approach

Intuition

This problem is a textbook application of Binary Search. The range [1, n] is conceptually a sorted sequence, and the guess API acts as our comparator.

The core idea:

Maintain a search window [left, right]. Always guess the middle value. The API response tells us which half contains the answer, so we discard the other half.

Specifically:

  • Start with left = 1 and right = n.
  • Compute mid = left + (right - left) / 2.
  • Call guess(mid):
    • If it returns 0: mid is the answer. Return it.
    • If it returns -1: our guess is too high, so the answer is in [left, mid - 1]. Set right = mid - 1.
    • If it returns 1: our guess is too low, so the answer is in [mid + 1, right]. Set left = mid + 1.
  • Repeat until found.

Why does this always work? Because the answer is guaranteed to exist in the range [1, n], and at each step we provably keep the answer within our shrinking window. The window halves each iteration, so we converge in O(log n) steps.

Note the use of mid = left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow, which is critical here since n can be up to 2^31 - 1.

Step-by-Step

Let's trace through n = 10, pick = 6 using binary search:

Step 1: Initialize left = 1, right = 10. The search range is [1, 10].

Step 2: Compute mid = 1 + (10 - 1) / 2 = 5. Call guess(5). Returns 1 (too low). The pick is higher than 5. Set left = 6.

Step 3: Now left = 6, right = 10. Compute mid = 6 + (10 - 6) / 2 = 8. Call guess(8). Returns -1 (too high). The pick is lower than 8. Set right = 7.

Step 4: Now left = 6, right = 7. Compute mid = 6 + (7 - 6) / 2 = 6. Call guess(6). Returns 0 (correct!). Return 6.

Binary search found the answer in 3 guesses instead of 6!

Algorithm

  1. Initialize left = 1 and right = n.
  2. While left <= right:
    • Compute mid = left + (right - left) / 2 (prevents integer overflow).
    • Call result = guess(mid).
    • If result == 0, return mid — we found the picked number.
    • If result == -1, our guess is too high. Set right = mid - 1.
    • If result == 1, our guess is too low. Set left = mid + 1.
  3. The loop is guaranteed to find the answer before terminating (since pick is in [1, n]).

Code

// 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
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int result = guess(mid);
            
            if (result == 0) {
                return mid;
            } else if (result == -1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1; // Never reached
    }
};
# The guess API is already defined for you.
# @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
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        
        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)
            
            if result == 0:
                return mid
            elif result == -1:
                right = mid - 1
            else:
                left = mid + 1
        
        return -1  # Never reached
/* The guess API is defined in the parent class GuessGame.
   @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
   int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int result = guess(mid);
            
            if (result == 0) {
                return mid;
            } else if (result == -1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1; // Never reached
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each iteration, binary search halves the search range. Starting with n candidates, after k iterations we have n / 2^k candidates remaining. The loop terminates when n / 2^k ≤ 1, giving k = ⌈log₂(n)⌉. For the maximum constraint of n = 2^31 - 1, this is at most 31 iterations.

Space Complexity: O(1)

We only use three integer variables (left, right, mid) and one result variable. No additional data structures are allocated, and the algorithm is iterative (no recursion).