This problem relies on dynamic programming with a sliding window to track probabilities efficiently. By defining dp[x] as the probability of reaching exactly x points, you can accumulate probabilities from prior states. The final result sums dp[k] to dp[n], handling edge cases where k = 0 or maxPts is large to avoid redundant computation.
Problem Statement
Alice plays a card-based game starting with 0 points and draws numbers while her total is less than k. Each draw adds an integer randomly from 1 to maxPts, inclusive, with all outcomes equally likely.
She stops drawing when her total reaches k or more points. The task is to calculate the probability that Alice's final score does not exceed n, accounting for all random draw sequences.
Examples
Example 1
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Alice gets a single card, then stops.
Example 2
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
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
Example details omitted.
Constraints
- 0 <= k <= n <= 104
- 1 <= maxPts <= 104
Solution Approach
Define DP State
Let dp[x] represent the probability that Alice reaches exactly x points. Initialize dp[0] = 1, since she starts with zero points.
Use Sliding Window Sum
Instead of summing all prior probabilities for each dp[x], maintain a running sum of the last maxPts dp values to calculate dp[x] in O(1) per step. This leverages the equal probability distribution and reduces time complexity.
Aggregate Final Probability
Sum all dp[x] for x from k to n to get the total probability of Alice finishing with at most n points. Handle k = 0 separately, where Alice stops immediately with probability 1.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) using sliding window accumulation for dp, and space complexity is O(n) to store the DP array. Without sliding window optimization, naive DP would be O(n*maxPts).
What Interviewers Usually Probe
- Candidate defines dp[x] clearly and explains why each state depends on previous maxPts states.
- Candidate optimizes naive DP using a sliding window to reduce time complexity.
- Candidate correctly handles edge cases like k = 0 or n < k without overcounting probabilities.
Common Pitfalls or Variants
Common pitfalls
- Attempting naive summation of all prior states for each dp[x], leading to TLE.
- Forgetting to cap the probability sum at n, causing overestimation.
- Not accounting for k = 0, which should immediately return 1.0 probability.
Follow-up variants
- Change maxPts to a non-uniform probability distribution for each draw, requiring weighted DP.
- Compute expected value instead of probability, altering the DP recurrence slightly.
- Consider multiple players drawing sequentially, updating DP to track joint probabilities.
How GhostInterview Helps
- GhostInterview provides step-by-step DP table construction to visualize state transitions.
- It highlights when sliding window optimization is necessary to avoid performance pitfalls.
- It auto-checks edge cases and probability accumulation to prevent common miscalculations.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main DP pattern in New 21 Game?
The core pattern is state transition dynamic programming, tracking the probability of each point total and accumulating over previous maxPts states.
Why use a sliding window in this problem?
Sliding window efficiently computes dp[x] by summing the previous maxPts probabilities in O(1) per step, avoiding O(n*maxPts) computation.
How do we handle k = 0 in New 21 Game?
If k = 0, Alice draws no cards and the probability of being at most n is 1, since she stops immediately.
Can this method handle large maxPts values?
Yes, sliding window ensures that even large maxPts do not lead to excessive computation, keeping time complexity linear in n.
How do we compute the final probability?
Sum dp[x] for all x between k and n inclusive, as these represent all possible outcomes where Alice stops at or below n points.
Need direct help with New 21 Game instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture New 21 Game from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the probability that soup A empties before soup B using state transition dynamic programming efficiently.
Open problem page#1227 Airplane Seat Assignment ProbabilityCalculate the probability that the last passenger sits in their assigned seat using state transition dynamic programming for airplanes.
Open problem page#1467 Probability of a Two Boxes Having The Same Number of Distinct BallsCompute the probability that two boxes contain the same number of distinct balls using careful combinatorial and DP methods.
Open problem page