Problem Description

The "Guess Number Higher or Lower" problem asks you to guess a number that was picked from the range 1 to n. The chosen number is called pick. You are provided with a function guess(num) which returns:

• -1 if num is higher than pick
• 1 if num is lower than pick
• 0 if num is equal to pick

• There is exactly one valid answer between 1 and n.
• You should minimize the number of calls to guess.

Thought Process

At first glance, we might consider checking every number from 1 to n in order, calling guess(num) for each. However, this would be inefficient, especially for large n, since it could require up to n calls.
Instead, we realize that the guess function tells us whether our guess is too high or too low. This is similar to searching for a number in a sorted list, where we can use the information to eliminate half of the remaining possibilities each time. This is the classic "binary search" approach, which is much more efficient than checking each number one by one.

Solution Approach

We use binary search to efficiently narrow down the possible values for pick:

1. Initialize two pointers: low = 1 and high = n.
2. While low is less than or equal to high:
   • Calculate mid = low + (high - low) // 2 (to avoid overflow).
   • Call guess(mid):
     • If the result is 0, we've found pick and return mid.
     • If the result is -1, mid is too high, so set high = mid - 1.
     • If the result is 1, mid is too low, so set low = mid + 1.
3. Repeat until the number is found.

We use binary search because it reduces the search space by half with each guess, making it highly efficient even for large values of n.

Example Walkthrough

Let's say n = 10 and pick = 6.

• Start: low = 1, high = 10
• First guess: mid = (1 + 10) // 2 = 5. guess(5) returns 1 (too low), so set low = 6.
• Second guess: mid = (6 + 10) // 2 = 8. guess(8) returns -1 (too high), so set high = 7.
• Third guess: mid = (6 + 7) // 2 = 6. guess(6) returns 0 (correct!).

The function finds the correct answer in just 3 guesses, rather than checking every number from 1 to 10.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n), as you might have to check every number from 1 to n.
• Space Complexity: O(1), since only a few variables are used.

• Time Complexity: O(log n), because the search space is halved with each guess.
• Space Complexity: O(1), as only pointers and a variable for the guess are needed.

The binary search approach is much more efficient and is preferred for large n.

Summary

The "Guess Number Higher or Lower" problem is elegantly solved using binary search, leveraging the feedback from the guess API to halve the search space at each step. This approach minimizes the number of guesses required, making it highly efficient even for large input sizes. The key insight is to recognize the similarity to searching in a sorted list and apply the binary search algorithm accordingly.

Code Implementation

# The guess API is already defined for you.
# def guess(num: int) -> int:

def guessNumber(n: int) -> int:
    low, high = 1, n
    while low <= high:
        mid = low + (high - low) // 2
        res = guess(mid)
        if res == 0:
            return mid
        elif res < 0:
            high = mid - 1
        else:
            low = mid + 1

// The API guess is defined for you.
// 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 never reach here
}

/* The guess API is defined in the parent class GuessGame.
   int guess(int num); */

public class Solution extends GuessGame {
    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 never reach here
    }
}

/** 
 * Forward declaration of guess API.
 * @param {number} num
 * @return {number}
 * var guess = function(num) {}
 */

var guessNumber = function(n) {
    let low = 1, high = n;
    while (low <= high) {
        let mid = Math.floor(low + (high - low) / 2);
        let res = guess(mid);
        if (res === 0) return mid;
        else if (res < 0) high = mid - 1;
        else low = mid + 1;
    }
    return -1; // Should never reach here
};