We are playing the Guessing Game. The game will work as follows:
1 and n.x, you will pay x dollars. 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 <= 200Problem Overview: You pick a number between 1 and n. Every wrong guess costs the value of the guessed number. The goal is to determine the minimum amount of money required to guarantee a win regardless of which number is chosen.
Approach 1: Recursive Game Simulation (Exponential Time, O(2^n) time, O(n) space)
This problem can be modeled as a minimax game. For each possible guess k between l and r, you pay k and the game continues either in the left range [l, k-1] or the right range [k+1, r]. Since the opponent can force the worst outcome, you take the maximum cost of the two branches. The optimal choice minimizes this worst-case cost across all guesses. A pure recursive solution recomputes the same ranges repeatedly, leading to exponential time complexity.
Approach 2: Dynamic Programming with Memoized Recursion (O(n^3) time, O(n^2) space)
The key observation is that subproblems repeat for the same interval [l, r]. Store results in a 2D DP table where dp[l][r] represents the minimum guaranteed cost for that range. For each interval, iterate every possible pivot k, compute k + max(dp[l][k-1], dp[k+1][r]), and choose the minimum across all pivots. Memoization avoids recomputation and turns the exponential recursion into polynomial time. This approach is a classic interval DP pattern frequently seen in dynamic programming and adversarial decision problems related to game theory. The numeric nature of the cost also ties the reasoning to math based minimax optimization.
Recommended for interviews: Interviewers expect the memoized dynamic programming solution. Start by describing the recursive minimax idea to show understanding of the game strategy. Then introduce memoization or a DP table to remove overlapping subproblems. This demonstrates both problem modeling and optimization skills.
This approach involves using dynamic programming with recursion to solve the problem. The main idea is to break the problem into subproblems: determining the cost of guessing any number within a given range. For each number in the current range, calculate the worst-case cost of guessing that number, accounting for both possibilities where the picked number is less or greater than the guessed number. Store solutions to subproblems to avoid recalculating them.
The code defines a function getMoneyAmount that uses a 2D array dp to store the minimum cost for each subproblem. It iteratively calculates the minimum cost for increasing intervals, considering each number in the interval as a potential guess and calculating the worst-case cost. The main program calls this function with n = 10 and outputs the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3) due to the three nested loops through possible ranges and guesses.
Space Complexity: O(n^2) for storing results of subproblems.
A more advanced recursive approach with memoization achieves similar results, storing results of previously solved subproblems in a cache for fast retrieval. This is especially useful for large inputs, reducing computational overhead by avoiding repeated calculations of the same conditions and ranges.
This recursive solution uses a helper function minCost that utilizes memoization to cache results of subproblems in a table dp. The getMoneyAmount function initializes the cache and invokes the helper for the full range from 1 to n, ensuring that calculations are only done once per subproblem.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), reduced with memoization.
Space Complexity: O(n^2), for memoizing results.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Recursion | Time Complexity: O(n^3) due to the three nested loops through possible ranges and guesses. |
| Optimized Recursive Memoization | Time Complexity: O(n^2), reduced with memoization. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pure Recursive Game Simulation | O(2^n) | O(n) | Conceptual understanding of the minimax decision process before optimization |
| Dynamic Programming with Memoized Recursion | O(n^3) | O(n^2) | Standard interview solution that removes overlapping subproblems |
| Optimized Recursive Memoization | O(n^3) | O(n^2) | Same DP strategy with pruning and cleaner recursion for practical implementations |
Guess Number Higher or Lower - Leetcode 374 - Python • NeetCode • 38,553 views views
Watch 9 more video solutions →Practice Guess Number Higher or Lower II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor