New 21 Game
MedPrompt
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 <= 1041 <= maxPts <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
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
-
- Handle the edge case where the answer is trivially 1.0 (if
k=0orn >= k + maxPts - 1).
- Handle the edge case where the answer is trivially 1.0 (if
-
- Initialize a
dparray of sizen+1to store probabilities. Setdp[0] = 1.0.
- Initialize a
-
- Iterate
ifrom 1 ton.
- Iterate
-
- Inside this loop, iterate
jfrom 1 tomaxPts.
- Inside this loop, iterate
-
- If the previous score
p = i - jis valid (i.e.,p >= 0andp < k), adddp[p] / maxPtstodp[i].
- If the previous score
-
- After filling the
dparray, initialize a variableresult = 0.0.
- After filling the
-
- Iterate
ifromktonand sum updp[i]intoresult.
- Iterate
-
- Return
result.
- Return
Walkthrough
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
Time
O(n * maxPts). The outer loop runs `n` times, and the inner loop runs `maxPts` times.
Space
O(n) to store the `dp` array.
Trade-offs
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.
This approach optimizes the naive DP solution. We observe that the calculation of dp[i] involves summing up a window of previous dp values. Instead of re-calculating this sum every time, we can maintain the sum in a 'sliding window' and update it in O(1) time for each step.
Algorithm
-
- Handle edge cases (
k=0orn >= k + maxPts - 1).
- Handle edge cases (
-
- Initialize a
dparray of sizen+1. Setdp[0] = 1.0.
- Initialize a
-
- Initialize
windowSum = 1.0(fordp[0]) andresult = 0.0.
- Initialize
-
- Iterate
ifrom 1 ton.
- Iterate
-
- Calculate
dp[i] = windowSum / maxPts.
- Calculate
-
- If
i < k, adddp[i]towindowSumbecause it's a score from which we can continue drawing.
- If
-
- If
i >= k, adddp[i]toresultbecause it's a final score within our target range.
- If
-
- If
i >= maxPts, subtractdp[i - maxPts]fromwindowSumas it slides out of the window of the lastmaxPtsscores.
- If
-
- Return
result.
- Return
Walkthrough
The recurrence dp[i] = (1/maxPts) * sum(dp[p]) for p in a certain range suggests an optimization. The sum is over a contiguous block of previous dp values.
Let windowSum be the sum of probabilities of scores from which Alice is allowed to draw a card. Initially, Alice is at score 0, so dp[0] = 1.0 and windowSum = 1.0.
We iterate from i = 1 to n. At each step i, dp[i] is calculated as windowSum / maxPts.
After calculating dp[i], we update windowSum for the next iteration i+1. The new window for i+1 is [i+1-maxPts, i]. Compared to the window for i ([i-maxPts, i-1]), we add dp[i] and remove dp[i-maxPts].
The update rule for windowSum depends on whether we can continue drawing from score i.
- If
i < k, we can continue drawing. So, we adddp[i]towindowSum. - If
i >= k, we must stop.dp[i]represents the probability of a final state. We add it to our finalresultbut not towindowSum, because we cannot draw any more cards from this state.
As we slide the window, we also need to subtract the term that falls out of the window's left end. If i >= maxPts, we subtract dp[i - maxPts] from windowSum.
This way, windowSum is always maintained as sum(dp[j]) over the relevant window, and each dp[i] is computed in O(1) time.
The final result is the sum of 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; double windowSum = 1.0; double result = 0.0; for (int i = 1; i <= n; i++) { dp[i] = windowSum / maxPts; if (i < k) { windowSum += dp[i]; } else { result += dp[i]; } if (i >= maxPts) { windowSum -= dp[i - maxPts]; } } return result;}Complexity
Time
O(n). We iterate through the scores from 1 to `n` once, and all operations inside the loop are constant time.
Space
O(n) for the `dp` array. We need to store `dp` values because `dp[i]` depends on `dp[i-maxPts]`.
Trade-offs
Pros
Highly efficient with linear time complexity.
Passes all test cases within the time limit.
Cons
The logic for updating the sliding window sum can be slightly tricky to get right, especially around the
kboundary.
Solutions
Solution
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; }}class Solution {public: double new21Game(int n, int k, int maxPts) { vector<double> f(k); function<double(int)> dfs = [&](int i) -> double { if (i >= k) { return i <= n ? 1 : 0; } if (i == k - 1) { return min(n - k + 1, maxPts) * 1.0 / maxPts; } if (f[i]) { return f[i]; } return f[i] = dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts; }; return dfs(0); }};class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float: @ cache def dfs(i: int) -> float: if i >= k: return int(i <= n) if i == k - 1: return min(n - k + 1, maxPts) / maxPts return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts return dfs(0)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.