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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Guess Number Higher or Lower II

Number: 375

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer n, you are playing a guessing game where a number is chosen from 1 to n. Each time you guess a number and you are wrong, you pay the value of that guess. The objective is to determine the minimum amount of money required to guarantee a win, regardless of which number is chosen.

Key Insights

  • Use dynamic programming to solve the problem by considering every possible pivot number.
  • Define a state dp[i][j] that represents the minimum cost required to guarantee a win for the range [i, j].
  • For a guess k in the range [i, j], the worst-case cost is k plus the maximum cost required between the left interval [i, k-1] and right interval [k+1, j].
  • The recurrence relation is: dp[i][j] = min(i ≤ k ≤ j){ k + max(dp[i][k-1], dp[k+1][j]) }.
  • The base condition is dp[i][j] = 0 when i >= j, since no cost is required when there is only one number or an invalid range.

Space and Time Complexity

Time Complexity: O(n^3) – The solution considers each pair (i, j) and for each such pair, iterates through all possible pivot values k. Space Complexity: O(n^2) – A two-dimensional dp table is used to store subproblem solutions.

Solution

The problem is solved using a bottom-up dynamic programming approach. We initialize a dp table where dp[i][j] stores the minimal cost of guaranteeing a win for the number range [i, j]. For every possible interval [i, j], we iterate through every possible guess k and calculate the cost for that guess as k plus the maximum cost between the two resulting intervals (i.e. the worst-case scenario). The minimum cost among these is stored in dp[i][j]. This ensures that we consider the worst-case in every subproblem ensuring a guaranteed win strategy in the overall game.

Code Solutions

# Python implementation for Guess Number Higher or Lower II

def getMoneyAmount(n: int) -> int:
    # Create a DP table with dimensions (n+2) x (n+2)
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    
    # Fill the DP table from shorter intervals to longer intervals
    for length in range(2, n + 1):  # length is the interval length
        for start in range(1, n - length + 2):
            end = start + length - 1
            dp[start][end] = float('inf')
            for pivot in range(start, end + 1):
                # cost when choosing pivot as the guess number
                # for out of bound intervals, cost=0
                cost = pivot + max(dp[start][pivot - 1], dp[pivot + 1][end])
                dp[start][end] = min(dp[start][end], cost)
    return dp[1][n]

# Example usage:
print(getMoneyAmount(10))  # Expected output: 16
← Back to All Questions