New 21 Game - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Alice draws numbers between 1 and maxPts until her score reaches at least k. The task is to compute the probability that her final score is less than or equal to n. Each draw is equally likely, so the problem becomes a probability DP where each state depends on the previous maxPts states.
Approach 1: Dynamic Programming (Brute Transition) (Time: O(n * maxPts), Space: O(n))
Define dp[i] as the probability that Alice reaches exactly i points. Start with dp[0] = 1. For each score i, distribute its probability to the next maxPts states because Alice can draw any value from 1 to maxPts. In practice, compute dp[i] by summing probabilities from the previous maxPts states and dividing by maxPts. Once the score reaches k, Alice stops drawing, so those states contribute directly to the final probability if i ≤ n. This method is straightforward but inefficient because every state recomputes a sum over up to maxPts previous probabilities.
Approach 2: Dynamic Programming with Sliding Window (Time: O(n), Space: O(n))
The transition in the naive DP repeatedly sums the same range of probabilities. Replace that repeated summation with a sliding window. Maintain a running window sum of the previous maxPts probabilities that can still draw cards (scores less than k). Compute dp[i] = windowSum / maxPts. If i < k, add dp[i] into the window because Alice can keep drawing from that score. If i - maxPts was previously part of the window, subtract it to maintain the correct range. This converts the expensive repeated summation into constant-time updates while iterating once through the states. The final answer is the sum of dp[i] for all i from k to n.
This technique is a classic combination of dynamic programming and a sliding window optimization applied to a probability process. The DP models the probability of reaching each score, while the window tracks the active range of states that can still transition forward. Understanding this transition compression is common in interview problems involving probability and stochastic processes.
Recommended for interviews: The dynamic programming with sliding window approach. The naive DP shows you understand the probabilistic recurrence, but interviewers expect the O(n) optimization that avoids recomputing range sums. Implementing the sliding window correctly demonstrates strong DP intuition and attention to transition efficiency.
Approach 1: Dynamic Programming with Sliding Window
The idea is to use an array to keep track of the probability of reaching exactly a particular score. We will use a sliding window approach to maintain the sum of probabilities for the most recent maxPts scores dynamically. This allows us to efficiently update probabilities as we simulate Alice drawing numbers up to n.
In this Python implementation, we initialize a probability array dp where dp[i] represents the probability of having exactly i points. The window sum is managed carefully so that only relevant probabilities affect the current probability determination. By sliding the window sum, we efficiently update the probabilities.
Complexity
The time complexity is O(n), given we loop from 0 to n. The space complexity is also O(n) due to the dp storage.
Approach 2: Memoized Search
We design a function dfs(i), which represents the probability that when the current score is i, the final score does not exceed n when we stop drawing numbers. The answer is dfs(0).
The calculation method of function dfs(i) is as follows:
- If
i \ge k, then we stop drawing numbers. Ifi \le n, return1, otherwise return0; - Otherwise, we can draw the next number
jin the range[1,..maxPts], thendfs(i) = \frac{1}{maxPts} sum_{j=1}^{maxPts} dfs(i+j).
Here we can use memoized search to accelerate the calculation.
The time complexity of the above method is O(k times maxPts), which will exceed the time limit, so we need to optimize it.
When i \lt k, the following equation holds:
$
\begin{aligned}
dfs(i) &= (dfs(i + 1) + dfs(i + 2) + cdots + dfs(i + maxPts)) / maxPts & (1)
\end{aligned}
When i \lt k - 1, the following equation holds:
\begin{aligned}
dfs(i+1) &= (dfs(i + 2) + dfs(i + 3) + cdots + dfs(i + maxPts + 1)) / maxPts & (2)
\end{aligned}
Therefore, when i \lt k-1, we subtract equation (2) from equation (1) to get:
\begin{aligned}
dfs(i) - dfs(i+1) &= (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts
\end{aligned}
That is:
\begin{aligned}
dfs(i) &= dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts
\end{aligned}
If i=k-1, we have:
\begin{aligned}
dfs(i) &= dfs(k - 1) = (dfs(k) + dfs(k + 1) + cdots + dfs(k + maxPts - 1)) / maxPts & (3)
\end{aligned}
We assume there are i numbers not exceeding n, then k+i-1 leq n, and since ileq maxPts, we have i leq min(n-k+1, maxPts), so equation (3) can be written as:
\begin{aligned}
dfs(k-1) &= min(n-k+1, maxPts) / maxPts
\end{aligned}
In summary, we have the following state transition equation:
\begin{aligned}
dfs(i) &= \begin{cases}
1, & i geq k, i leq n \
0, & i geq k, i \gt n \
min(n-k+1, maxPts) / maxPts, & i = k - 1 \
dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts, & i < k - 1
\end{cases}
\end{aligned}
Time complexity O(k + maxPts), space complexity O(k + maxPts). Where k$ is the maximum score.
Code
Python
Java
C++
Go
TypeScript
Approach 3: Dynamic Programming
We can convert the memoized search in Solution 1 into dynamic programming.
Define f[i] to represent the probability that when the current score is i, the final score does not exceed n when we stop drawing numbers. The answer is f[0].
When k leq i leq min(n, k + maxPts - 1), we have f[i] = 1.
When i = k - 1, we have f[i] = min(n-k+1, maxPts) / maxPts.
When i \lt k - 1, we have f[i] = f[i + 1] + (f[i + 1] - f[i + maxPts + 1]) / maxPts.
Time complexity O(k + maxPts), space complexity O(k + maxPts). Where k is the maximum score.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sliding Window | The time complexity is O(n), given we loop from 0 to n. The space complexity is also O(n) due to the |
| Memoized Search | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Naive Transitions) | O(n * maxPts) | O(n) | Useful for understanding the probability recurrence and deriving the state transition. |
| Dynamic Programming with Sliding Window | O(n) | O(n) | Optimal solution for interviews and production. Avoids repeated range summations. |
Video Solution
New 21 Game - Leetcode 837 - Python • NeetCodeIO • 21,400 views views
Watch 9 more video solutions →Frequently Asked Questions
Is New 21 Game easy or hard?
New 21 Game Python/Java solution
How to solve New 21 Game in O(n)?
What is the best approach for New 21 Game?
Is New 21 Game asked at Google/Amazon/Meta?
What data structure is used in New 21 Game?
What is the time complexity of New 21 Game?
Ready to solve this problem?
Practice New 21 Game with our built-in code editor and test cases.
Practice on FleetCode