Get started

Guess Number Higher or Lower II — Medium Problem & Solution

A host secretly picks an integer between 1 and n. You guess repeatedly.

Problem statement

A host secretly picks an integer between 1 and n. You guess repeatedly. When you guess the number you win; when you guess some x that is wrong you pay x coins, and the host tells you whether the secret is higher or lower than x.

Return the smallest amount of money that guarantees a win no matter which number the host picked — that is, the cost of your best strategy against its worst-case secret.

Example 1

Input: n = 10
Output: 16
Explanation: Open with 7. If the secret is higher, guess 9 next (at most 7 + 9 = 16 paid); if lower, guess 3 and then 1 or 5 (at most 7 + 3 + 5 = 15). A last remaining number is always guessed for free, and no strategy gets by on 15.

Example 2

Input: n = 1
Output: 0
Explanation: The only possible number is guessed for free.

Example 3

Input: n = 5
Output: 6
Explanation: Guess 4; if lower, guess 2 — the worst case pays 4 + 2.

Constraints

  • 1 <= n <= 200

How to solve Guess Number Higher or Lower II

A minimax over intervals: you choose the guess (minimise), the host chooses the side that hurts you most (maximise). Only the remaining interval matters, so memoise on (lo, hi).

Approach

  1. dp[lo][hi] = 0 when lo >= hi (zero or one candidate left — guessing it is free).
  2. For intervals of increasing length: dp[lo][hi] = min over g of g + max(dp[lo][g-1], dp[g+1][hi]).
  3. Return dp[1][n].

Why it works

If you guess g and it is wrong you pay g and the host can steer you into whichever side is more expensive, so g + max(...) is exactly the guaranteed cost of opening with g; you then pick the best opening. Sub-intervals are independent of how you reached them, so the recurrence is exact.

Complexity

  • Time — O(n³)
  • Space — O(n²)

Pitfalls

  • Guessing correctly costs nothing, so a single remaining number costs 0, and two numbers {a, a+1} cost a (guess the smaller).
  • Binary search is not optimal: for n = 5 it would guess 3 first and pay 3 + 4 = 7 in the worst case, more than 6.
  • Fill the table by increasing interval length.

Reference solution

Python

def getMoneyAmount(n: int) -> int:
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(2, n + 1):
        for lo in range(1, n - length + 2):
            hi = lo + length - 1
            best = 10**9
            for g in range(lo, hi + 1):
                left = dp[lo][g - 1]
                right = dp[g + 1][hi]
                cost = g + (left if left > right else right)
                if cost < best:
                    best = cost
            dp[lo][hi] = best
    return dp[1][n]

JavaScript

var getMoneyAmount = function(n) {
    var dp = [];
    for (var i = 0; i < n + 2; i++) dp.push(new Array(n + 2).fill(0));
    for (var len = 2; len <= n; len++) {
        for (var lo = 1; lo + len - 1 <= n; lo++) {
            var hi = lo + len - 1;
            var best = Infinity;
            for (var g = lo; g <= hi; g++) {
                var cost = g + Math.max(dp[lo][g - 1], dp[g + 1][hi]);
                if (cost < best) best = cost;
            }
            dp[lo][hi] = best;
        }
    }
    return dp[1][n];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 307 math problems · the whole catalogue

Learn the technique: Dynamic Programming