DSA problem
New 21 Game
Alice plays a card game similar in spirit to Blackjack. She starts with 0 points and keeps drawing cards while her current total is strictly less than k. Each draw yields an integer uniformly at random from 1 to maxPts inclusive. Once Alice's total reaches k or more she stops drawing. Return the probability that her final total is at most n.
Let dp[i] denote the probability that Alice's running total is exactly i at some point during the game. We initialise dp[0] = 1 because she starts on zero. For any i with i < k Alice will draw again, contributing a uniform 1/maxPts of dp[i] to each of dp[i + 1], dp[i + 2], ..., dp[i + maxPts]. For i >= k Alice has stopped, so no more outgoing transitions from those states. The answer is therefore sum of dp[i] for k <= i <= n.
A direct double loop over i and the maxPts outcomes runs in O(n * maxPts) time, which is too slow given the input limits. The key insight is that for any i with i < k, dp[i] equals (dp[i - 1] + dp[i - 2] + ... + dp[i - maxPts]) / maxPts — the average of a sliding window of length maxPts ending at i - 1, restricted to indices below k because higher indices do not contribute new draws.
The optimal implementation keeps a running sum windowSum of dp[max(0, i - maxPts)..i - 1] capped to indices strictly less than k. As i increases by one we add dp[i - 1] to the window (only if i - 1 < k) and subtract dp[i - 1 - maxPts] if it just left the window (and was below k). Each dp[i] is computed in O(1) after the window update, giving a total O(n) time and O(n) space algorithm.
Examples
n = 10, k = 1, maxPts = 101.0n = 6, k = 1, maxPts = 100.6n = 21, k = 17, maxPts = 100.73278Constraints
- 0 <= k <= n <= 10^4
- 1 <= maxPts <= 10^4
- If k == 0 the answer is exactly 1.0 (Alice draws nothing and her total is 0 <= n).
- Answers within 1e-5 of the true probability are accepted.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.