AlgoMaster Logo

New 21 Game

mediumFrequency6 min readUpdated June 23, 2026

Understanding the Problem

Alice draws cards one at a time. Each card gives her a random number of points between 1 and maxPts, with equal probability (so each value has probability 1/maxPts). She keeps drawing as long as her total is strictly less than k. Once her total reaches k or more, she stops.

We need the probability that her final total is at most n.

The last draw determines the final score. Alice stops the moment her total reaches k or more, so the final draw must start from some score in [k - maxPts, k - 1] (any lower and she would have stopped already). The final score therefore falls in the range [k, k - 1 + maxPts]. We want the probability that this final score is at most n.

Two cases make the answer trivially 1. If k == 0, Alice never draws, stays at 0 points, and 0 <= n. If n >= k - 1 + maxPts, then every possible ending score is at most n. Both return 1.

For the general case, we build up the probability of reaching each score, then sum the probabilities of all valid final scores.

Key Constraints:

  • 0 <= k <= n <= 10^4 --> The final scores of interest span at most maxPts values starting at k, and n is at most 10,000, so a dp array of size n + 1 fits in memory. A recurrence that scans up to maxPts previous scores per step costs O(n * maxPts), which reaches 10^8 in the worst case and is too slow.
  • 1 <= maxPts <= 10^4 --> Each step depends on a contiguous window of up to maxPts previous probabilities. A running sum over that window removes the inner O(maxPts) loop and drops the work to O(n).

Approach 1: Recursive DP (Brute Force)

Intuition

Define dp[i] as the probability that Alice has exactly i points at some moment during the game. Alice starts at 0, so dp[0] = 1. From any score j < k, Alice draws a card valued 1 through maxPts, each with probability 1/maxPts, and moves to score j + card.

So the probability of reaching score i is:

dp[i] = sum of dp[j] / maxPts for all valid j where j = i - maxPts to j = i - 1 and j >= 0 and j < k.

The condition j < k matters because if Alice is at score j >= k, she has already stopped and won't draw more cards.

The answer is the sum of dp[i] for all i from k to n.

Algorithm

  1. If k == 0 or n >= k + maxPts - 1, return 1.0 (all outcomes are valid).
  2. Create a dp array of size n + 1. Set dp[0] = 1.0.
  3. For each score i from 1 to n, compute dp[i] = sum(dp[j] for j in range(max(0, i - maxPts), min(i, k))) / maxPts.
  4. Return the sum of dp[i] for i from k to n.

Example Walkthrough

Trace n = 4, k = 4, maxPts = 3. Alice keeps drawing while her score is below 4, and each draw adds 1, 2, or 3 points with probability 1/3. We want the probability her final score is at most 4.

1Initialize: dp[0] = 1.0 (Alice starts at score 0)
0
1
start
1
0
2
0
3
0
4
0
1/6

Code

The inner loop recomputes the same sum from scratch at every step, even though the set of summed indices barely changes between consecutive i. The next approach maintains that sum incrementally and removes the inner loop entirely.

Approach 2: DP with Sliding Window (Optimal)

Intuition

The recurrence for dp[i] sums a contiguous window of previous dp values, restricted to indices that represent a "still drawing" state:

dp[i] = (sum of dp[j] for j from i - maxPts to i - 1, keeping only j in [0, k-1]) / maxPts

The window of summed indices moves by exactly one position as i increases by one: index i - 1 may enter on the right and index i - 1 - maxPts leaves on the left. So instead of recomputing the sum, maintain a running windowSum and adjust it by two O(1) operations per step, which brings the time from O(n * maxPts) down to O(n).

Two boundary rules keep windowSum equal to the correct restricted sum:

  • Add dp[i] to windowSum only when i < k. A score of k or above is a stopping state, so it never serves as the source of another draw and must not appear in any future window.
  • Subtract dp[i - maxPts] once i - maxPts >= 0. A draw adds at most maxPts, so score i is unreachable from any source more than maxPts below it.

Algorithm

  1. If k == 0 or n >= k + maxPts - 1, return 1.0.
  2. Create dp array of size n + 1. Set dp[0] = 1.0.
  3. Initialize windowSum = 1.0 (the window starts with only dp[0]).
  4. For each score i from 1 to n:
    • Set dp[i] = windowSum / maxPts.
    • If i < k, add dp[i] to windowSum (this score can contribute to future scores).
    • If i - maxPts >= 0, subtract dp[i - maxPts] from windowSum (this score falls out of the window).
  5. Sum dp[k] through dp[n] for the answer.

Example Walkthrough

Trace the same input as Approach 1, n = 4, k = 4, maxPts = 3, so the two methods can be compared directly. Watch windowSum grow while scores stay below k and shrink once a score drops more than maxPts behind the current index. The final dp array matches Approach 1 exactly, but it is built with one division, one addition, and one subtraction per step instead of an inner loop.

1Initialize: dp[0]=1.0, windowSum=1.0
0
1
windowSum=1.0
1
0
2
0
3
0
4
0
1/6

Code