Guess Number Higher or Lower II

Medium

Asked by:

19 views

Topics:

Dynamic Programming

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

I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
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.
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.

Example 1:

Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
    - If this is my number, your total is $0. Otherwise, you pay $7.
    - If my number is higher, the range is [8,10]. Guess 9.
        - If this is my number, your total is $7. Otherwise, you pay $9.
        - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
        - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
    - If my number is lower, the range is [1,6]. Guess 3.
        - If this is my number, your total is $7. Otherwise, you pay $3.
        - If my number is higher, the range is [4,6]. Guess 5.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
            - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
            - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
        - If my number is lower, the range is [1,2]. Guess 1.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
            - If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

Example 2:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

Example 3:

Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is $0. Otherwise, you pay $1.
    - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

Constraints:

1 <= n <= 200

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input 'n'? Is there a maximum value for 'n'?
If I don't guess the correct number within the given range, what should my strategy be?
Should I assume 'n' is always a positive integer greater than or equal to 1?
Can you clarify what happens if my initial guess is higher than the correct number? Do I still incur the cost of that guess?
Are we optimizing for minimizing the worst-case cost, or is there some other optimization target?

Brute Force Solution

Approach

The goal is to find the minimum amount of money we need to guarantee a win in a number guessing game. The brute force approach involves trying every possible guess and calculating the worst-case cost for each guess.

Here's how the algorithm would work step-by-step:

Consider every number within the given range as our initial guess.
For each possible guess, imagine the other player tells us whether our guess was too high or too low.
If the guess was too low, we now know the number is higher than our guess, so we need to apply this strategy to the remaining higher numbers.
If the guess was too high, we now know the number is lower than our guess, so we need to apply this strategy to the remaining lower numbers.
Calculate the cost of each guess by adding the guess itself to the worst-case scenario cost (either the 'too low' or 'too high' case). This worst-case scenario is the maximum of the two cases.
Repeat this process for all possible guesses in each remaining range (either higher or lower).
After we have done this for all numbers in the original range, we pick the initial guess that had the lowest worst-case cost. This is the minimum amount of money needed to guarantee a win.

Code Implementation

def get_money_amount(number):    def calculate_minimum_cost(start, end):        if start >= end:            return 0        minimum_worst_case_cost = float('inf')        for guess in range(start, end + 1):            # Determine the worst case scenario in either direction            cost_if_guess_is_wrong = guess + max(calculate_minimum_cost(start, guess - 1), \
                                                 calculate_minimum_cost(guess + 1, end))            # We want to minimize the maximum possible cost, so find minimum            minimum_worst_case_cost = min(minimum_worst_case_cost, cost_if_guess_is_wrong)        return minimum_worst_case_cost    # Initiate the recursive brute force search    return calculate_minimum_cost(1, number)

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm considers every number within the range [1, n] as a potential guess. For each guess, it recursively explores the lower and higher ranges. The core operation involves iterating through subranges to determine the minimum cost for each possible guess. This leads to a nested loop structure within the recursive calls, as we consider each number within a subrange. The overall complexity is therefore O(n^3) because for each of n guesses we are potentially solving two subproblems each of size n and it costs n to find the min/max of the two resulting solutions.

Space Complexity

O(N^2) – The algorithm uses dynamic programming to store the minimum cost to guarantee a win for subranges of the numbers from 1 to n. It implicitly uses a 2D array, dp, of size N x N, where N is the input n. Each cell dp[i][j] stores the minimum cost to guess a number in the range [i, j]. Therefore, the auxiliary space used is proportional to the size of this DP table, which grows quadratically with the input size n, resulting in a space complexity of O(N^2).

Optimal Solution

Approach

This problem is about finding the minimum cost to guarantee a win in a number guessing game. Instead of guessing randomly, we use a strategy to pick numbers that minimize the worst-case scenario, ensuring we don't spend too much even if we're unlucky.

Here's how the algorithm would work step-by-step:

Imagine you have a range of numbers to guess from.
Think about what would happen if you guessed a specific number.
If you guess right, great, you're done! But what if you're wrong?
If you're wrong, you'll need to guess either higher or lower, and you'll have to pay for your incorrect guess.
The goal is to pick a first guess such that, no matter whether you need to go higher or lower, the remaining cost is as small as possible.
Consider each number in the range as a potential first guess.
For each potential first guess, figure out the maximum cost you might have to pay if you're wrong (either by going higher or lower).
Pick the number that has the smallest of these maximum costs. This minimizes the worst case scenario.
Use a method where you solve smaller subproblems and store those answers to build up to the final answer. For example, calculate how much it would cost if the range was only 1 to 2, then 1 to 3, and so on.
The answer is the minimum cost you figured out using this bottom-up approach.

Code Implementation

def get_money_amount(maximum_number) -> int:
    dp_table = [[0] * (maximum_number + 1) for _ in range(maximum_number + 1)]

    for length in range(2, maximum_number + 1):
        for start in range(1, maximum_number - length + 2):
            end = start + length - 1
            dp_table[start][end] = float('inf')

            # Try each number in range as a guess
            for guess in range(start, end):

                # Minimize the worst-case scenario
                cost = guess + max(dp_table[start][guess - 1], dp_table[guess + 1][end])
                dp_table[start][end] = min(dp_table[start][end], cost)

    # The result is stored in the top-right corner of the table.
    return dp_table[1][maximum_number]

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm employs dynamic programming to solve the problem. It iterates through all possible subranges of the input range [1, n]. The outer loops consider all possible lengths of subranges, leading to approximately n iterations. For each subrange, it iterates through all possible guess numbers within that subrange. For each possible guess, it considers the maximum cost of the two subproblems (guessing higher or lower). This innermost operation takes constant time, but is nested within the two range loops, so overall we have roughly n * n * n operations. Therefore, the time complexity is O(n^3).

Space Complexity

O(N^2) – The described dynamic programming approach stores intermediate results for subproblems to avoid redundant calculations. Specifically, it builds a table (often called 'dp') where dp[i][j] stores the minimum cost to guess the number within the range [i, j]. This table has dimensions N x N, where N is the upper bound of the initial range. Therefore, the auxiliary space used to store the dynamic programming table is proportional to N squared.

Edge Cases

Case	How to Handle
n = 1 (Only one number to guess)	The cost is zero as you automatically guess the number.
n = 2 (Two numbers to guess)	The optimal guess is 1, with a maximum cost of 1 if incorrect.
n = 0 (Invalid input)	Return 0 as there is no range to guess from.
Large n, causing potential stack overflow with naive recursion	Use dynamic programming (memoization) to avoid recomputation and limit recursion depth.
Integer overflow when calculating the cost (mid + i)	Use long data types to prevent integer overflow during cost calculations, especially with large n.
The algorithm is inefficient for very large n	Ensure that the dynamic programming approach is implemented correctly to achieve optimal time complexity O(n^2).
The minimum value is chosen every time	The DP approach should consider all possible guesses and choose the one minimizing the worst-case cost.
Input 'n' as a negative number	Return 0, throw an exception, or handle negative inputs based on problem constraints.

n = 1 (Only one number to guess)

How to Handle:

The cost is zero as you automatically guess the number.

n = 2 (Two numbers to guess)

How to Handle:

The optimal guess is 1, with a maximum cost of 1 if incorrect.

n = 0 (Invalid input)

How to Handle:

Return 0 as there is no range to guess from.

Large n, causing potential stack overflow with naive recursion

How to Handle:

Use dynamic programming (memoization) to avoid recomputation and limit recursion depth.

Integer overflow when calculating the cost (mid + i)

How to Handle:

Use long data types to prevent integer overflow during cost calculations, especially with large n.

The algorithm is inefficient for very large n

How to Handle:

Ensure that the dynamic programming approach is implemented correctly to achieve optimal time complexity O(n^2).

The minimum value is chosen every time

How to Handle:

The DP approach should consider all possible guesses and choose the one minimizing the worst-case cost.

Input 'n' as a negative number

How to Handle:

Return 0, throw an exception, or handle negative inputs based on problem constraints.