algoadvance

Leetcode 375. Guess Number Higher or Lower II

Problem Statement

We are playing the Guessing Game. The game is as follows:

1. I pick a number between 1 and n.
2. You have to guess which number I picked.
3. Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
4. However, instead of a simple comparison, you need to determine the amount of money you need to guarantee a win.

The solution should calculate the minimum amount of money required to guarantee a win if you guess the numbers strategically.

Example:

Input: n = 10
Output: 16
Explanation: The strategy might be to go with number 7 first: 
  * If you guess 7, and it is wrong, there are two scenarios:
    - Number is greater (possible numbers: 8, 9, 10). From here, the worst case would require 8 units to guarantee a win.
    - Number is lesser (possible numbers: 1, 2, 3, 4, 5, 6). From here, the worst case would require 10 units to guarantee a win.
  * Choosing 7 first will ensure the minimum cost in the worst-case scenario.

Clarifying Questions

1. What happens if the initial number guessed turns out to be the correct one?
   • If the initial guess is correct, the cost is $0 because we win without any further guesses.
2. Are we always guessing one number at a time or can we guess ranges?
   • We are guessing one number at a time.
3. Is the goal to minimize the maximum amount we might have to pay?
   • Yes, we have to minimize the maximum amount we might have to pay in the worst-case scenario.

Strategy

To solve this problem, we will use a dynamic programming approach. The idea is to minimize the cost for each range [i, j] in a systematic manner.

• Define dp[i][j] as the minimum amount of money required to guarantee a win for the range [i, j].
• The base case is dp[i][i] = 0 because if there’s only one number, we pick it, and the cost is $0.
• For each possible range [i, j], consider each number k in that range.
  • The cost of choosing k is k + max(dp[i][k-1], dp[k+1][j]) (since it covers the worst-case scenario).
  • We’ll iterate through all k in [i, j] and choose the k which minimizes this cost.

Code

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int getMoneyAmount(int n) {
        // Create a 2D DP array initialized to 0
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        
        // Only consider ranges of length greater than 1
        for (int length = 2; length <= n; ++length) {
            for (int i = 1; i <= n - length + 1; ++i) {
                int j = i + length - 1;
                dp[i][j] = INT_MAX;
                // Consider every number k in the range [i, j] as the initial guess
                for (int k = i; k < j; ++k) {
                    // Calculate the worst cost if we pick k as the guess stop point
                    int cost = k + max(dp[i][k - 1], dp[k + 1][j]);
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }
        
        return dp[1][n];
    }
};

Time Complexity

The time complexity of this algorithm is (O(n^3)) due to the three nested loops:

• The outer loop iterates through the length of ranges.
• The second loop iterates through the starting points of ranges.
• The innermost loop considers each possible guess within the current range.

The space complexity is (O(n^2)) for storing the results in the dynamic programming table dp.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?