Jobs

Interviews

Discussions

New 21 Game

Medium

Asked by:

11 views

Topics:

Dynamic Programming

Alice plays the following game, loosely based on the card game "21".

Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets k or more points.

Return the probability that Alice has n or fewer points.

Answers within 10^-5 of the actual answer are considered accepted.

Example 1:

Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.

Example 2:

Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.

Example 3:

Input: n = 21, k = 17, maxPts = 10
Output: 0.73278

Constraints:

0 <= k <= n <= 10⁴
1 <= maxPts <= 10⁴

Try coding it in LeetCode

New 21 Game

Medium

Asked by:

11 views

Topics:

Dynamic Programming

Alice plays the following game, loosely based on the card game "21".

Alice stops drawing numbers when she gets k or more points.

Return the probability that Alice has n or fewer points.

Answers within 10^-5 of the actual answer are considered accepted.

Example 1:

Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.

Example 2:

Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.

Example 3:

Input: n = 21, k = 17, maxPts = 10
Output: 0.73278

Constraints:

0 <= k <= n <= 10⁴
1 <= maxPts <= 10⁴

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:

Can W, K, and N be zero? What are the maximum values for W, K, and N?
What is considered winning? Is it inclusive or exclusive of the range [K, N]?
If K is greater than N, should I return 1.0? Is K always less than or equal to N+1?
Can W be larger than N? If so, what does that imply about the starting hand?
If there are multiple ways to win (or probabilities very close to 1), what level of precision do you expect in the return value?

Brute Force Solution

Approach

The brute force approach to this card game involves simulating every possible game scenario. We explore all the ways to draw cards until the game ends, either by exceeding a target score or stopping beforehand. By exhaustively checking each scenario, we determine the likelihood of winning.

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

Begin with a score of zero.
Consider all possible first card draws, from 1 to the maximum card value.
For each possible card draw, add it to the current score.
If the new score is at or above the target score, check if it's within the winning range and record the outcome (win or lose).
If the new score is below the target score, consider all possible next card draws (again, from 1 to the maximum card value).
Continue adding card draws and checking scores until each branch of possible draws either exceeds the maximum score or a player decides to stop drawing.
Keep track of how many times the final score falls within the winning range.
After exploring all possible scenarios, calculate the probability of winning by dividing the number of winning outcomes by the total number of outcomes.

Code Implementation

def new_21_game_brute_force(maximum_number, end_range, maximum_card):
    total_outcomes = 0
    winning_outcomes = 0

    def play_game(current_score):
        nonlocal total_outcomes, winning_outcomes
        
        # Increment total outcomes, because we've reached a terminal state
        total_outcomes += 1

        if current_score >= end_range and current_score <= maximum_number:
            # We have a winning hand
            winning_outcomes += 1
            return
        
        if current_score > maximum_number:
            # We bust
            return

        # Recursively simulate next card draws to explore further scenarios
        for card_value in range(1, maximum_card + 1):

            play_game(current_score + card_value)

    play_game(0)

    if total_outcomes == 0:
        return 0.0

    return winning_outcomes / total_outcomes

Big(O) Analysis

Time Complexity

O((maxDraw)^{targetScore}) – The brute force approach explores all possible game scenarios by simulating every card draw. Each draw has 'maxDraw' possibilities (1 to maxDraw). The depth of the recursion can go up to the 'targetScore' because we keep drawing cards until we reach or exceed the target score. Therefore, the total number of possible scenarios grows exponentially with the target score and maxDraw, resulting in a time complexity of O((maxDraw)^{targetScore}).

Space Complexity

O(K^W) – The brute force approach explores all possible game scenarios by simulating card draws recursively. The depth of the recursion is determined by how many cards can be drawn before reaching or exceeding the target score K, and each level of the recursion has W possible branches (the possible card values from 1 to maxPts). Therefore, the maximum depth of the recursive call stack can be proportional to K, and each call can branch out to W possibilities, leading to a space complexity of O(W^K) in the worst-case scenario, where W represents the maximum card value. If we consider the number of winning numbers to be K and number of draw values to be W then the height of the tree will be proportional to K and branching factor W giving auxiliary space usage of approximately O(W^K).

Optimal Solution

Approach

The core idea is to calculate the winning probability directly, rather than simulating the game. We can do this using dynamic programming, working backwards from the end to the beginning.

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

Figure out the basic winning strategy: if you are already at or above the target number, you win automatically. Any number greater than the max draw value plus the target is an automatic loss.
Create a 'table' that stores the probability of winning from each possible starting number.
Start filling the table backwards, from higher numbers down to lower numbers.
For each number, calculate the win probability. It's the average of winning probabilities you can reach by drawing any card.
The winning probability of a starting number is influenced by how many cards we can draw and what range they are within.
The final answer is the winning probability from the very beginning, which is a particular cell in our completed 'table'.

Code Implementation

def new_21_game(maximum_points, k_value, maximum_draw):
    if maximum_points >= k_value + maximum_draw or k_value == 0:
        return 1.0

    # This array stores the win probability for each score.
    win_probability = [0.0] * (maximum_points + 1)

    # Initialize winning probabilities for scores >= k_value
    for current_score in range(k_value, maximum_points + 1):
        win_probability[current_score] = 1.0

    sum_of_probabilities = sum(win_probability[k_value:])

    # Calculate probabilities backward from k_value - 1 down to 0.
    for current_score in range(k_value - 1, -1, -1):
        win_probability[current_score] = sum_of_probabilities / maximum_draw

        # Adjust rolling sum for the next iteration.
        sum_of_probabilities -= win_probability[current_score + maximum_draw] if current_score + maximum_draw <= maximum_points else 0
        sum_of_probabilities += win_probability[current_score]

    # Return the probability of winning starting from score 0.
    return win_probability[0]

Big(O) Analysis

Time Complexity

O(maxPts) – The algorithm iterates backwards from K to 0, calculating the win probability for each score. The outer loop runs 'maxPts' times in the worst case. Inside the loop, for each score, the win probability is calculated by averaging the win probabilities of scores achievable by drawing a card, up to 'maxPts' away. Therefore, the inner calculations take a constant time, dependent on maxPts, but do not add additional nested loops. The overall time complexity is then directly proportional to the value of maxPts.

Space Complexity

O(K + maxPts) – The auxiliary space is dominated by the 'table' mentioned in the explanation, which stores the probability of winning from each possible starting number. The size of this table depends on the target number, K, and the maximum possible points, maxPts, which determines the range of starting numbers we need to consider. Therefore, the space complexity is O(K + maxPts), as we need to store win probabilities for all values from 0 up to (K + maxPts - 1).

Edge Cases

Case	How to Handle
N, K, maxPts are all zero.	Return 1.0 as Alice starts with 0 and doesn't draw, already satisfying the win condition if K is 0.
K is 0 and N is greater than 0	Return 1.0 because Alice already has a winning hand.
N is greater than or equal to K + maxPts - 1 (maximum possible score)	Alice is guaranteed to win, so return 1.0.
maxPts is 0 and K > 0	Alice can never draw, so if her initial score is below K, she loses, return 0.0
K is a large number (close to int max) but maxPts is small, can cause issues with array allocation	The dp array size depends on k and n, but since the problem constraints limit k and n to 10000, this isn't an issue.
N is much smaller than K	The probability should be 0 because Alice needs at least K to win.
Integer overflow when calculating window sum	The problem constraints for maxPts and K ensure that the window sum calculation won't lead to integer overflow.
maxPts = 1	The algorithm should still work, just the window update will be smaller.

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:

Can W, K, and N be zero? What are the maximum values for W, K, and N?
What is considered winning? Is it inclusive or exclusive of the range [K, N]?
If K is greater than N, should I return 1.0? Is K always less than or equal to N+1?
Can W be larger than N? If so, what does that imply about the starting hand?
If there are multiple ways to win (or probabilities very close to 1), what level of precision do you expect in the return value?

Brute Force Solution

Approach

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

Begin with a score of zero.
Consider all possible first card draws, from 1 to the maximum card value.
For each possible card draw, add it to the current score.
If the new score is at or above the target score, check if it's within the winning range and record the outcome (win or lose).
If the new score is below the target score, consider all possible next card draws (again, from 1 to the maximum card value).
Continue adding card draws and checking scores until each branch of possible draws either exceeds the maximum score or a player decides to stop drawing.
Keep track of how many times the final score falls within the winning range.
After exploring all possible scenarios, calculate the probability of winning by dividing the number of winning outcomes by the total number of outcomes.

Code Implementation

def new_21_game_brute_force(maximum_number, end_range, maximum_card):
    total_outcomes = 0
    winning_outcomes = 0

    def play_game(current_score):
        nonlocal total_outcomes, winning_outcomes
        
        # Increment total outcomes, because we've reached a terminal state
        total_outcomes += 1

        if current_score >= end_range and current_score <= maximum_number:
            # We have a winning hand
            winning_outcomes += 1
            return
        
        if current_score > maximum_number:
            # We bust
            return

        # Recursively simulate next card draws to explore further scenarios
        for card_value in range(1, maximum_card + 1):

            play_game(current_score + card_value)

    play_game(0)

    if total_outcomes == 0:
        return 0.0

    return winning_outcomes / total_outcomes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The core idea is to calculate the winning probability directly, rather than simulating the game. We can do this using dynamic programming, working backwards from the end to the beginning.

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

Figure out the basic winning strategy: if you are already at or above the target number, you win automatically. Any number greater than the max draw value plus the target is an automatic loss.
Create a 'table' that stores the probability of winning from each possible starting number.
Start filling the table backwards, from higher numbers down to lower numbers.
For each number, calculate the win probability. It's the average of winning probabilities you can reach by drawing any card.
The winning probability of a starting number is influenced by how many cards we can draw and what range they are within.
The final answer is the winning probability from the very beginning, which is a particular cell in our completed 'table'.

Code Implementation

def new_21_game(maximum_points, k_value, maximum_draw):
    if maximum_points >= k_value + maximum_draw or k_value == 0:
        return 1.0

    # This array stores the win probability for each score.
    win_probability = [0.0] * (maximum_points + 1)

    # Initialize winning probabilities for scores >= k_value
    for current_score in range(k_value, maximum_points + 1):
        win_probability[current_score] = 1.0

    sum_of_probabilities = sum(win_probability[k_value:])

    # Calculate probabilities backward from k_value - 1 down to 0.
    for current_score in range(k_value - 1, -1, -1):
        win_probability[current_score] = sum_of_probabilities / maximum_draw

        # Adjust rolling sum for the next iteration.
        sum_of_probabilities -= win_probability[current_score + maximum_draw] if current_score + maximum_draw <= maximum_points else 0
        sum_of_probabilities += win_probability[current_score]

    # Return the probability of winning starting from score 0.
    return win_probability[0]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
N, K, maxPts are all zero.	Return 1.0 as Alice starts with 0 and doesn't draw, already satisfying the win condition if K is 0.
K is 0 and N is greater than 0	Return 1.0 because Alice already has a winning hand.
N is greater than or equal to K + maxPts - 1 (maximum possible score)	Alice is guaranteed to win, so return 1.0.
maxPts is 0 and K > 0	Alice can never draw, so if her initial score is below K, she loses, return 0.0
K is a large number (close to int max) but maxPts is small, can cause issues with array allocation	The dp array size depends on k and n, but since the problem constraints limit k and n to 10000, this isn't an issue.
N is much smaller than K	The probability should be 0 because Alice needs at least K to win.
Integer overflow when calculating window sum	The problem constraints for maxPts and K ensure that the window sum calculation won't lead to integer overflow.
maxPts = 1	The algorithm should still work, just the window update will be smaller.