We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Guess Number Higher or Lower II

Difficulty: Medium

Problem Description

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

  1. I pick a number between 1 and n.
  2. You guess a number.
  3. If you guess the right number, you win the game.
  4. 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.
  5. Every time you guess a wrong number 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.

Key Insights

  • The problem can be solved using Dynamic Programming.
  • The optimal strategy involves minimizing the maximum cost incurred from guessing.
  • For each number guessed, we need to consider the worst-case scenario of the remaining range.
  • We can build a DP table where dp[i][j] represents the minimum cost to guarantee a win for the range [i, j].

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Solution

To solve the problem, we can use Dynamic Programming (DP). We will create a 2D DP array where dp[i][j] represents the minimum cost to guarantee a win for the range of numbers from i to j. The approach is as follows:

  1. Initialize a DP table of size n x n, where n is the input number.
  2. Fill the table for ranges of increasing lengths.
  3. For each range [i, j], iterate through all possible guesses k between i and j. The cost for each guess k is k plus the maximum cost of either the left or right sub-range (i.e., dp[i][k-1] or dp[k+1][j]).
  4. Update dp[i][j] with the minimum cost found among all possible guesses.

This way, we ensure that we are considering all possible scenarios and taking the one that guarantees the least cost.

Code Solutions

def getMoneyAmount(n):
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    for length in range(2, n + 1):  # length of the range
        for i in range(1, n - length + 2):  # starting point
            j = i + length - 1  # ending point
            dp[i][j] = float('inf')
            for k in range(i, j):  # possible guesses
                cost = k + max(dp[i][k-1], dp[k+1][j])
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]
← Back to All Questions