algoadvance

Leetcode 375. Guess Number Higher or Lower II

Problem Statement:

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

Given a particular n, return the minimum amount of money you need to guarantee a win, regardless of which number I pick.

Clarifying Questions:

  1. What is the range of n?
    Let’s assume 1 ≤ n ≤ 200.

  2. Is this a dynamic programming problem?
    Yes, this problem can be approached using dynamic programming.

  3. Do we consider the cost of correct guesses?
    No, only the cost of incorrect guesses is considered.

  4. Are the guesses sequential or can they be in any order?
    The guesses can be in any order, but we need to find a strategy that minimizes the total cost.

Strategy:

  1. Dynamic Programming Approach:
    • Define dp[i][j] as the minimum cost required to guess the right number in the range [i, j].
    • Base Case:
      • If i == j, dp[i][j] = 0, because no cost is incurred if the range has only one number.
      • If i > j, dp[i][j] = 0, because it’s an invalid range.
    • Recursive Step:
      • For each possible guess k in the range [i, j], the cost we pay is k + max(dp[i][k-1], dp[k+1][j]). This is because if we guess k, the cost is k. If the actual number is lower we need to pay dp[i][k-1], if it’s higher we pay dp[k+1][j].
      • We strive to minimize this maximum cost.
  2. Implementation in Java:
public class Solution {

    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 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] = 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];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getMoneyAmount(10)); // Example test case
    }
}

Time Complexity:

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

  1. The outermost loop iterates over the length of the ranges.
  2. The second loop iterates over the starting point i of the range.
  3. The innermost loop iterates over all possible guesses k within the range [i, j].

Since we are considering all subranges and possible guesses for these subranges, the cubic complexity is justified. This is acceptable given the constraint ( n \leq 200 ).

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