Guess Number Higher or Lower

NeetCode: Guess Number Higher or Lower · LeetCode: 374. Guess Number Higher or Lower · Difficulty: Easy

A number between 1 and n has been picked. You can call guess(num), which returns -1 if num is higher than the picked number, 1 if num is lower, and 0 if num is the picked number. Return the picked number.

Example

Text

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

LeetCode supplies guess as a method of a hidden base class GuessGame, and the solution class extends it. The programs below declare a small GuessGame that stores the secret pick and counts calls, so Solution calls guess(num) exactly as it does on LeetCode.

Brute force: try every number

Guess 1, 2, 3, ... until the API returns 0. This ignores the direction returned by guess, so the worst case makes n calls.

Java

class GuessGame {
    private final int pick;
    int calls = 0;

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

    int guess(int num) {
        calls++;
        return Integer.compare(pick, num);
    }
}

class Solution extends GuessGame {
    Solution(int pick) {
        super(pick);
    }

    public int guessNumber(int n) {
        for (int num = 1; num <= n; num++) {
            if (guess(num) == 0) {
                return num;
            }
        }
        return -1;
    }
}

public class Main {
    static void run(int n, int pick) {
        Solution s = new Solution(pick);
        int answer = s.guessNumber(n);
        System.out.println("n=" + n + " pick=" + pick + " -> " + answer + " (" + s.calls + " calls)");
    }

    public static void main(String[] args) {
        run(10, 6);
        run(1, 1);
        run(2_000_000_000, 5);
    }
}

Output

n=10 pick=6 -> 6 (6 calls)
n=1 pick=1 -> 1 (1 calls)
n=2000000000 pick=5 -> 5 (5 calls)

Integer.compare(pick, num) returns -1, 0, or 1, which is the same contract as guess: -1 when num is above the pick.

Time: O(n) calls. Space: O(1).

Optimal: binary search

Each answer rules out half of the remaining range: -1 means the pick is smaller than num, 1 means it is larger. Keep an inclusive range [lo, hi] and guess the middle. Compute the middle as lo + (hi - lo) / 2, because lo + hi can overflow int and wrap to a negative number when n is near Integer.MAX_VALUE.

Java

class GuessGame {
    private final int pick;
    int calls = 0;

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

    int guess(int num) {
        calls++;
        return Integer.compare(pick, num);
    }
}

class Solution extends GuessGame {
    Solution(int pick) {
        super(pick);
    }

    public int guessNumber(int n) {
        int lo = 1;
        int hi = n;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int result = guess(mid);
            if (result == 0) {
                return mid;
            } else if (result < 0) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }
}

public class Main {
    static void run(int n, int pick) {
        Solution s = new Solution(pick);
        int answer = s.guessNumber(n);
        System.out.println("n=" + n + " pick=" + pick + " -> " + answer + " (" + s.calls + " calls)");
    }

    public static void main(String[] args) {
        run(10, 6);
        run(1, 1);
        run(2_000_000_000, 5);
        run(Integer.MAX_VALUE, Integer.MAX_VALUE);
    }
}

Output

n=10 pick=6 -> 6 (3 calls)
n=1 pick=1 -> 1 (1 calls)
n=2000000000 pick=5 -> 5 (30 calls)
n=2147483647 pick=2147483647 -> 2147483647 (31 calls)

Time: O(log n) calls. Space: O(1).

The last call in main uses n = Integer.MAX_VALUE. With (lo + hi) / 2 the sum would wrap to a negative int; lo + (hi - lo) / 2 stays in range.