Guess Number Higher or Lower II
MedPrompt
We are playing the Guessing Game. The game will work as follows:
- I pick a number between
1andn. - You guess a number.
- If you guess the right number, you win the game.
- If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
- Every time you guess a wrong number
x, you will payxdollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
Example 1:
Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
- If this is my number, your total is $0. Otherwise, you pay $7.
- If my number is higher, the range is [8,10]. Guess 9.
- If this is my number, your total is $7. Otherwise, you pay $9.
- If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
- If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
- If my number is lower, the range is [1,6]. Guess 3.
- If this is my number, your total is $7. Otherwise, you pay $3.
- If my number is higher, the range is [4,6]. Guess 5.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
- If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
- If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
- If my number is lower, the range is [1,2]. Guess 1.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.Example 2:
Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.Example 3:
Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
- If this is my number, your total is $0. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.
Constraints:
1 <= n <= 200
Approaches
3 approaches with complexity analysis and trade-offs.
This approach solves the problem iteratively using bottom-up dynamic programming, also known as tabulation. It avoids recursion and its associated overhead, often leading to better performance. We use a 2D table, dp[i][j], to store the minimum cost to guarantee a win for the number range [i, j]. The key idea is to fill this table by starting with the smallest subproblems (ranges of length 2) and progressively building up to the solution for the full range [1, n]. By iterating through range lengths, we ensure that when we calculate dp[i][j], the solutions for all smaller, required subproblems (like dp[i][k-1] and dp[k+1][j]) have already been computed and stored in the table.
Algorithm
- Create a 2D DP table
dpof size(n+2) x (n+2)and initialize all its values to 0. The extra padding helps handle boundary cases likek-1andk+1without extra checks. - Iterate over the length of the range,
len, from 2 ton. - Inside this loop, iterate over all possible starting points
ifor a range of lengthlen. The loop foriwill go from 1 up ton - len + 1. - Calculate the end point of the current range:
j = i + len - 1. - For the current range
[i, j], initialize its costdp[i][j]toInteger.MAX_VALUE. - Iterate through all possible first guesses
kfromitoj. - For each guess
k, calculate the cost using the already computed values from smaller sub-ranges:cost = k + max(dp[i][k-1], dp[k+1][j]). - Update the minimum cost for the range
[i, j]:dp[i][j] = min(dp[i][j], cost). - After all loops complete, the value
dp[1][n]will contain the minimum cost to guarantee a win for the entire range[1, n]. Return this value.
Walkthrough
Instead of starting from the top problem (1, n) and breaking it down, the bottom-up approach starts with the smallest problems and builds up. We use a 2D array dp[n+2][n+2] where dp[i][j] stores the solution for the subproblem on the range [i, j]. The base cases are ranges of length 0 or 1, for which the cost is 0. Our DP table is initialized to 0, which covers these cases. We then iterate on the length of the range, len, from 2 to n. For each len, we iterate through all possible start indices i. The end index j is simply i + len - 1. For each range [i, j], we calculate dp[i][j] by trying every possible split point k (our first guess) from i to j. The cost for guessing k is k + max(dp[i][k-1], dp[k+1][j]). Since we are iterating by increasing length, the values dp[i][k-1] (for range length k-i) and dp[k+1][j] (for range length j-k) are guaranteed to have been computed in previous iterations. We take the minimum cost over all possible k. The final answer is the value stored in dp[1][n].
public class Solution { public int getMoneyAmount(int n) { if (n == 1) { return 0; } // dp[i][j] = min cost for range [i, j] int[][] dp = new int[n + 2][n + 2]; for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE; for (int k = i; k <= j; k++) { int cost = k + Math.max(dp[i][k - 1], dp[k + 1][j]); dp[i][j] = Math.min(dp[i][j], cost); } } } return dp[1][n]; }}Complexity
Time
O(n^3). The three nested loops for `len`, `i`, and `k` dominate the runtime. `len` runs up to `n`, `i` runs up to `n`, and `k` runs up to `n` times in the worst case.
Space
O(n^2), for the 2D DP table.
Trade-offs
Pros
Generally the most efficient solution for the given constraints due to the absence of recursion overhead.
Iterative nature can make it easier to analyze and debug.
Guarantees the optimal solution.
Cons
Can be slightly less intuitive to formulate than the recursive top-down approach.
Still has a cubic time complexity, which might be too slow for much larger constraints.
This approach directly translates the problem's logic into a recursive function. For any given range of numbers [start, end], we explore every possible number x as our first guess. The cost associated with guessing x is x plus the cost of the subsequent worst-case scenario. The worst-case scenario is the one that costs more: either guessing in the lower sub-range [start, x-1] or the higher sub-range [x+1, end]. We then choose the guess x that minimizes this total worst-case cost. This method explores the entire tree of possibilities without any optimization.
Algorithm
- Define a recursive function
solve(start, end)that returns the minimum cost to guarantee a win for the range[start, end]. - Base Case: If
start >= end, it means there is at most one number in the range. We can guess it correctly on the first try, so the cost is 0. Return 0. - Initialize a variable
minCostto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through all possible first guesses
xfromstarttoend. - For each guess
x, calculate the cost if we choosex. This cost isx(for the current guess) plus the maximum cost of the subsequent subproblems, which ismax(solve(start, x - 1), solve(x + 1, end)). - Update
minCostwith the minimum cost found so far:minCost = min(minCost, currentCost). - After checking all possible guesses
x, returnminCost. - The initial call to find the solution for the range
[1, n]issolve(1, n).
Walkthrough
The problem asks for a strategy that minimizes the maximum possible cost, which is a classic minimax problem. We can define a function solve(start, end) that calculates the minimum cost to guarantee a win for a given range of numbers [start, end]. To compute this, we try every number x in the range as our first guess. If we guess x, we pay x dollars. The opponent then tells us if their number is higher or lower. To guarantee a win, we must prepare for the worst possible outcome. The cost for guessing x is x plus the cost of the harder of the two resulting subproblems: [start, x-1] or [x+1, end]. Therefore, the cost for a given guess x is x + max(solve(start, x-1), solve(x+1, end)). Our goal is to choose the guess x that minimizes this cost. This gives us the recurrence relation: solve(start, end) = min_{x=start..end} { x + max(solve(start, x-1), solve(x+1, end)) }. The base case for the recursion is when start >= end, which means there's at most one number left. We can guess it with no cost, so solve(start, end) = 0. This logic is implemented as a straightforward recursive function.
public class Solution { public int getMoneyAmount(int n) { return solve(1, n); } private int solve(int start, int end) { if (start >= end) { return 0; } int minCost = Integer.MAX_VALUE; for (int x = start; x <= end; x++) { int cost = x + Math.max(solve(start, x - 1), solve(x + 1, end)); minCost = Math.min(minCost, cost); } return minCost; }}Complexity
Time
Exponential, roughly O(n!). The function branches for each element in the range, and subproblems are recomputed many times. This is too slow for the given constraints.
Space
O(n), for the recursion stack depth. In the worst case, the recursion can go `n` levels deep.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem's recursive nature.
Provides a clear, albeit inefficient, baseline for solving the problem.
Cons
Extremely inefficient due to a massive number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for even small values of
n(e.g., n > 10).
This approach enhances the brute-force recursion by using memoization to eliminate redundant calculations. The core recursive logic remains the same, but we introduce a cache (typically a 2D array) to store the results of subproblems that have already been solved. Before computing the minimum cost for a range [start, end], we first check our cache. If the result is present, we use it directly. If not, we compute it, store it in the cache for future use, and then return it. This technique, also known as top-down dynamic programming, ensures that each unique subproblem is solved only once, dramatically improving the efficiency.
Algorithm
- Create a 2D array
memoof size(n+1) x (n+1)to store the results of subproblems. Initialize it with a value (e.g., 0 or -1) to indicate that a subproblem has not been solved. - Define a recursive helper function
solve(start, end). - Base Case: If
start >= end, return 0. - Memoization Check: If
memo[start][end]has already been computed (i.e., not the initial value), return it directly. - If not computed, initialize
minCosttoInteger.MAX_VALUE. - Iterate through all possible guesses
xfromstarttoend. - For each
x, recursively calculate the cost:cost = x + max(solve(start, x - 1), solve(x + 1, end)). - Update
minCost = min(minCost, cost). - Store Result: Before returning, store the computed minimum cost in the memoization table:
memo[start][end] = minCost. - Return
minCost. - The initial call is
solve(1, n).
Walkthrough
The plain recursive solution is slow because it repeatedly solves the same subproblems. For instance, solve(3, 5) might be needed when calculating solve(1, 10) (e.g., if we guess 2) and also when calculating solve(1, 8) (e.g., if we guess 2). To fix this, we can use a 2D array, memo[n+1][n+1], to store the results. memo[i][j] will hold the computed minimum cost for the range [i, j]. The recursive function solve(start, end) is modified to first check if memo[start][end] contains a pre-computed answer. If it does, the stored value is returned. Otherwise, the function proceeds with the calculation as in the brute-force approach. Once the result is found, it's stored in memo[start][end] before being returned. This ensures that the expensive computation for each subproblem (start, end) is performed only once.
public class Solution { private int[][] memo; public int getMoneyAmount(int n) { memo = new int[n + 1][n + 1]; return solve(1, n); } private int solve(int start, int end) { if (start >= end) { return 0; } if (memo[start][end] != 0) { return memo[start][end]; } int minCost = Integer.MAX_VALUE; // To reduce the search space, we can observe that the optimal first guess `x` // will likely be in the upper half of the range to balance the cost `x` // against the cost of the subproblems. We can start searching from the middle. for (int x = (start + end) / 2; x <= end; x++) { int cost = x + Math.max(solve(start, x - 1), solve(x + 1, end)); minCost = Math.min(minCost, cost); } memo[start][end] = minCost; return minCost; }}Complexity
Time
O(n^3). There are O(n^2) possible subproblems (ranges `[i, j]`). For each subproblem, we iterate up to `n` times to find the optimal guess `x`. Thus, the total complexity is O(n^2 * n) = O(n^3).
Space
O(n^2), primarily for the memoization table. The recursion stack depth adds an O(n) factor, but it's dominated by the table.
Trade-offs
Pros
Significantly more efficient than brute-force recursion, making it feasible for the given constraints.
Maintains the logical structure of the recursive solution, which can be easier to reason about.
Guarantees finding the optimal solution.
Cons
Requires O(n^2) space for the memoization table, which can be significant for very large
n.The recursive calls still have some overhead compared to a purely iterative solution.
Solutions
Solution
class Solution {public int getMoneyAmount(int n) { int[][] dp = new int[n + 10][n + 10]; for (int l = 2; l <= n; ++l) { for (int i = 1; i + l - 1 <= n; ++i) { int j = i + l - 1; dp[i][j] = Integer.MAX_VALUE; for (int k = i; k <= j; ++k) { int t = Math.max(dp[i][k - 1], dp[k + 1][j]) + k; dp[i][j] = Math.min(dp[i][j], t); } } } return dp[1][n]; }}class Solution {public: int getMoneyAmount(int n) { vector<vector<int>> dp(n + 10, vector<int>(n + 10)); for (int l = 2; l <= n; ++l) { for (int i = 1; i + l - 1 <= n; ++i) { int j = i + l - 1; dp[i][j] = INT_MAX; for (int k = i; k <= j; ++k) { int t = max(dp[i][k - 1], dp[k + 1][j]) + k; dp[i][j] = min(dp[i][j], t); } } } return dp[1][n]; }};class Solution : def getMoneyAmount ( self , n : int ) -> int : dp = [[ 0 ] * ( n + 10 ) for _ in range ( n + 10 )] for l in range ( 2 , n + 1 ): for i in range ( 1 , n - l + 2 ): j = i + l - 1 dp [ i ][ j ] = inf for k in range ( i , j + 1 ): t = max ( dp [ i ][ k - 1 ], dp [ k + 1 ][ j ]) + k dp [ i ][ j ] = min ( dp [ i ][ j ], t ) return dp [ 1 ][ n ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.