Guess Number Higher Or Lower

Problem Description

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

I choose a number from 1 to n. You have to guess which number I chose.

Every time you guess wrong, I will tell you whether the number I chose 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 chose (i.e. num > pick).
• 1: Your guess is lower than the number I chose (i.e. num < pick).
• 0: your guess is equal to the number I chose (i.e. num == pick).

Return the number that I chose.

Examples

Constraints

• 1 <= n <= 2³¹ - 1
• 1 <= pick <= n

Searching Integers Range via API Queries

We are searching for a target number within a continuous range [1, n]. We run binary search. Set left = 1 and right = n. At each step, calculate the midpoint mid = left + (right - left) / 2. Call the API: result = guess(mid).

• If result == 0, we have guessed correctly and return mid.
• If result == -1, our guess was too high, so we narrow the range to the left: right = mid - 1.
• If result == 1, our guess was too low, so we narrow the range to the right: left = mid + 1.

Solution 1: Binary Search with API Helper

Query the guess API to discard half of the search range at each step.

/** 
 * 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);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1;
        int right = n;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int res = guess(mid);
            if (res == 0) {
                return mid;
            } else if (res == -1) {
                right = mid - 1; // guess is too high
            } else {
                left = mid + 1; // guess is too low
            }
        }
        return -1;
    }
}

# 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 = 1
        right = n
        
        while left <= right:
            mid = left + (right - left) // 2
            res = guess(mid)
            if res == 0:
                return mid
            elif res == -1:
                right = mid - 1
            else:
                left = mid + 1
                
        return -1

/** 
 * 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 GuessGame {
public:
    int guessNumber(int n) {
        int left = 1;
        int right = n;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int res = guess(mid);
            if (res == 0) {
                return mid;
            } else if (res == -1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};

Complexity Analysis

• Time Complexity: O(log n) since we half the search range at each step.
• Space Complexity: O(1) auxiliary space as we search in place without allocating extra storage.

Where It Breaks

This implementation depends on a synchronous guess API response. If API calls are network-bound or asynchronous, the sequential loop structure must be converted to use callbacks or futures.

Common Mistakes

• Incorrect division syntax: In Python, using / which returns a float, instead of // for integer division.
• Integer overflow: Calculating mid as (left + right) / 2 which can exceed the maximum capacity of 32-bit signed integers when n is near 2^31 - 1.

Frequently Asked Questions

Why call the API instead of comparing numbers directly? The target pick is encapsulated inside the game object, representing standard client-server communication where the client does not have direct access to database state.

Does this algorithm always find the pick? Yes, since the search range covers every integer in [1, n] and the pick is guaranteed to exist within those boundaries.

← All Problems