New 21 Game

MEDIUM

Description

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⁴

Approaches

Checkout 2 different approaches to solve New 21 Game. Click on different approaches to view the approach and algorithm in detail.

Naive Dynamic Programming

This approach uses dynamic programming to solve the problem. We define dp[i] as the probability of reaching a score of exactly i. We build up the dp table from dp[0] up to dp[n]. The final answer is the sum of probabilities of stopping at scores from k to n.

Algorithm

1. Handle the edge case where the answer is trivially 1.0 (if k=0 or n >= k + maxPts - 1).
1. Initialize a dp array of size n+1 to store probabilities. Set dp[0] = 1.0.
1. Iterate i from 1 to n.
1. Inside this loop, iterate j from 1 to maxPts.
1. If the previous score p = i - j is valid (i.e., p >= 0 and p < k), add dp[p] / maxPts to dp[i].
1. After filling the dp array, initialize a variable result = 0.0.
1. Iterate i from k to n and sum up dp[i] into result.
1. Return result.

Let dp[i] be the probability of having a score of i at some point.

The base case is dp[0] = 1.0, as Alice starts with 0 points with certainty. All other dp values are initialized to 0.

To calculate dp[i], we consider all possible previous scores p from which we could reach i by drawing a single card j. The value of j can be from 1 to maxPts. So, p = i - j.

A crucial rule is that Alice only draws a card if her current score is less than k. Therefore, the previous score p must be less than k.

The probability of drawing any specific card j is 1 / maxPts.

The recurrence relation is: dp[i] = sum(dp[i-j] / maxPts) for j from 1 to maxPts, provided i-j >= 0 and i-j < k.

We iterate from i = 1 to n, and for each i, we iterate from j = 1 to maxPts to sum up the probabilities.

After computing all dp[i] up to n, the probability of stopping at a score i (where i >= k) is exactly dp[i]. This is because to reach i >= k, the previous score must have been < k.

The final answer is the sum of probabilities of stopping at any score between k and n, inclusive. This is sum(dp[i]) for i from k to n.

public double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k + maxPts - 1) {
        return 1.0;
    }
    double[] dp = new double[n + 1];
    dp[0] = 1.0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= maxPts; j++) {
            if (i - j >= 0 && i - j < k) {
                dp[i] += dp[i - j] / maxPts;
            }
        }
    }

    double probability = 0.0;
    for (int i = k; i <= n; i++) {
        probability += dp[i];
    }
    return probability;
}

Complexity Analysis

Time Complexity: O(n * maxPts). The outer loop runs `n` times, and the inner loop runs `maxPts` times.Space Complexity: O(n) to store the `dp` array.

Pros and Cons

Pros:

Simple to understand and implement.
Directly follows the problem's state transitions.

Cons:

Inefficient due to nested loops.
Time complexity is high, likely leading to 'Time Limit Exceeded' on larger test cases.

Code Solutions

Checking out 3 solutions in different languages for New 21 Game. Click on different languages to view the code.

class Solution {
private
  double[] f;
private
  int n, k, maxPts;
public
  double new21Game(int n, int k, int maxPts) {
    f = new double[k];
    this.n = n;
    this.k = k;
    this.maxPts = maxPts;
    return dfs(0);
  }
private
  double dfs(int i) {
    if (i >= k) {
      return i <= n ? 1 : 0;
    }
    if (i == k - 1) {
      return Math.min(n - k + 1, maxPts) * 1.0 / maxPts;
    }
    if (f[i] != 0) {
      return f[i];
    }
    return f[i] = dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts;
  }
}

Video Solution

Watch the video walkthrough for New 21 Game

Patterns:

MathSliding WindowDynamic ProgrammingProbability and Statistics