algoadvance

We are playing the game “Guess the Number.” The game is as follows:

I pick a number between 1 and n. You guess a number between 1 and n. If you guess the right number, you win the game. If you guess wrong, then I will tell you whether the number I picked is higher or lower than your guess, and you will continue guessing. Every time you guess a wrong number, you must pay the amount equal to the number you guessed. You win the game when you guess the correct number.

Given a particular n, find out how much money you need to have to guarantee a win.

Clarifying Questions

  1. Input: A single integer, n, which denotes the range [1, n] within which you need to guess the number.
  2. Output: A single integer, which is the minimum amount of money required to guarantee you can guess the correct number without running out of money.

Example

Input: n = 10
Output: 16

Strategy

The problem can be solved using a dynamic programming approach. Here’s the step-by-step strategy:

  1. State Definition: Let DP[i][j] be the minimum amount of money required to guarantee a win if the number to be guessed is between i and j.
  2. Base Case: For i == j, DP[i][j] = 0, because if there’s only one number to guess, no cost is required.
  3. Recurrence Relation:
    • For each number k guessed between i and j, the worst case cost is k plus the maximum of the cost between the splits [i, k-1] and [k+1, j] (as the actual number could be in either split).
    • Therefore, DP[i][j] = min(k + max(DP[i][k-1], DP[k+1][j])) for all k in [i, j].

Code

def getMoneyAmount(n: int) -> int:
    # Initialization of DP table with inf values
    DP = [[0] * (n+1) for _ in range(n+1)]
    
    # Fill DP table
    for length in range(2, n+1): # length of range to consider
        for start in range(1, n-length+2): # starting point of range
            end = start + length - 1 # ending point of range
            DP[start][end] = float('inf')
            for k in range(start, end+1):
                # DP value considering guessing k
                cost = k + max(DP[start][k-1] if k > start else 0, DP[k+1][end] if k < end else 0)
                DP[start][end] = min(DP[start][end], cost)
    
    return DP[1][n]

# Example test case
print(getMoneyAmount(10))  # Output: 16

Time Complexity

This approach ensures that you have the minimum guaranteed money to win the game.

Try our interview co-pilot at AlgoAdvance.com