algoadvance

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

Alice starts with 0 points, and draws numbers while her total is less than K. Each draw is an integer number between 1 and W (inclusive), where each draw is equally likely to be any of these integer numbers. Alice stops drawing numbers when she gets K or more points.

Return the probability that Alice’s score is less than or equal to N (that is, N or less) when she stops drawing.

Example 1:

Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.

Example 2:

Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.

Example 3:

Input: N = 21, K = 17, W = 10
Output: 0.73278

Note:

Clarifying Questions

  1. What happens if K is zero?
    • If K is zero, Alice can’t draw any card and thus will have 0 points, so the probability would be 1 if N >= 0, else 0.
  2. What if N is less than K?
    • If N is less than K, Alice will stop before reaching or exceeding K, so it’s certain Alice’s score will be less than or equal to N.

With these clarifications, we can move forward to devise the strategy.

Strategy

We’ll use Dynamic Programming (DP) to solve this problem. Let dp[x] represent the probability that Alice gets x points. We’ll construct dp array with the following considerations:

  1. Initialize dp[0] to 1 (100% chance Alice starts at 0 points).
  2. Iterate over x from 1 to N. Calculate dp[x] as the sum of dp[x-1] to dp[x-W] divided by W.
  3. Sum up the probabilities for points greater or equal to K but less than or equal to N.

Code

def new21Game(N: int, K: int, W: int) -> float:
    if K == 0 or N >= K + W:
        return 1.0

    dp = [0.0] * (N + 1)
    dp[0] = 1.0

    window_sum = 1.0
    result = 0.0
    for i in range(1, N + 1):
        dp[i] = window_sum / W
        if i < K:
            window_sum += dp[i]
        else:
            result += dp[i]
        if i - W >= 0:
            window_sum -= dp[i - W]
    
    return result

# Test example
print(new21Game(10, 1, 10)) # Output should be 1.00000
print(new21Game(6, 1, 10))  # Output should be 0.60000
print(new21Game(21, 17, 10))# Output should be 0.73278

Time Complexity

The time complexity is O(N), as we iterate through the range from 1 to N once, and within each iteration, updating the window_sum takes O(1) time. Therefore, our solution is efficient and should handle the input constraints effectively.

Try our interview co-pilot at AlgoAdvance.com