Guess Number Higher or Lower

A number is picked from 1 to n, and you have to guess it. After each guess, a predefined function guess(num) tells you how you did:

Return the picked number. This is LeetCode 374.

Example 1
Input: n = 10, pick = 6
Output: 6
Example 2
Input: n = 1, pick = 1
Output: 1

How to Think About It

Step 1: This is the guessing game everyone knows

With "higher" and "lower" hints, the best strategy is to guess the middle of what is left. Each answer rules out half of the remaining numbers. From 1 to 100, it never takes more than 7 guesses, because 27 = 128.

Step 2: Map the hints to the search range

  • Start with lo = 1 and hi = n.
  • guess(mid) == -1 means mid is too high, so the number is below it: hi = mid - 1.
  • guess(mid) == 1 means mid is too low: lo = mid + 1.
  • guess(mid) == 0: return mid.

The signs are the easy part to get backwards: the API describes your guess compared with the pick, not the other way round.

Step 3: Watch the overflow

n can be 231 - 1. If lo and hi are both near that value, (lo + hi) / 2 overflows to a negative number. lo + (hi - lo) / 2 computes the same middle safely.

Walkthrough

n = 10, pick = 6:

lohiGuess (mid)AnswerNext range
11051: too low6 to 10
6108-1: too high6 to 7
6760: correctreturn 6

Java Solution

On LeetCode, guess is provided by a parent class. To make the code runnable on its own, this version includes a small guess method that compares with a stored pick.

Java
public class GuessNumberHigherLower {

    private final int pick;                // the hidden number (LeetCode hides this)

    GuessNumberHigherLower(int pick) {
        this.pick = pick;
    }

    // -1: the guess is too high, 1: too low, 0: correct
    int guess(int num) {
        return Integer.compare(pick, num);
    }

    public int guessNumber(int n) {
        int lo = 1;
        int hi = n;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;  // n can be 2^31 - 1, so (lo + hi) would overflow
            int answer = guess(mid);
            if (answer == 0) {
                return mid;
            } else if (answer < 0) {
                hi = mid - 1;              // our guess is too high
            } else {
                lo = mid + 1;              // our guess is too low
            }
        }
        return -1;                         // not reached for a valid game
    }

    public static void main(String[] args) {
        System.out.println(new GuessNumberHigherLower(6).guessNumber(10));   // 6
        System.out.println(new GuessNumberHigherLower(2147483647).guessNumber(2147483647));
        // 2147483647
    }
}

The original implementation, GuessNumberHigherLower.java, is on GitHub.

Complexity

  • Time: O(log n) calls to guess: at most 31 for any int range.
  • Space: O(1).