New 21 Game: A Clean & Simple Visual Guide

The Core Problem

The "New 21 Game" sounds like a casino problem, but it is entirely mathematical. Alice is drawing numbers completely at random from a range of $1$ to maxPts. She starts at $0$ and will fiercely keep drawing numbers until her total points reach or exceed a target threshold, k.

Your goal is to figure out the exact probability that when she finally stops, her total score is less than or equal to n.

• Example 1: Input: n = 21, k = 17, maxPts = 10 -> Output: 0.73278

The Naive Trap

A standard Dynamic Programming approach would calculate the probability of landing on score i by looking backward at all the ways to get there: adding up the probabilities of i - 1, i - 2, all the way to i - maxPts, and dividing by maxPts.

However, because n and maxPts can go up to $10,000$, a nested loop ($O(N \times \text{maxPts})$) will instantly result in a Time Limit Exceeded (TLE) error.

Interactive Visualization

To avoid the nested loop, we must use a Sliding Window. Instead of recalculating the sum of the previous maxPts probabilities every single time, we maintain a running total called Wsum.

Use the visualizer below to see exactly how Wsum slides forward, dropping old values and picking up new ones.

Sliding Window Dynamic Programming

Let's use a real-world analogy: A conveyor belt of probabilities.

Imagine you are standing at the end of a conveyor belt that holds exactly maxPts buckets.

1. The probability of landing on your current spot is simply the sum of the buckets currently on the belt (Wsum), divided by the number of dice sides (maxPts).
2. As you step forward to the next spot, the belt moves forward by one.
3. If you are still allowed to draw (your score < k): Your current probability bucket is placed onto the start of the conveyor belt.
4. If your oldest bucket falls off the end of the belt: You subtract its value from your total.

This mechanism allows us to calculate the probability of every single state in strictly $O(1)$ time, turning our nested loop into a lightning-fast single pass.

Code Implementations

Here is the production-ready logic applying the sliding window optimization.

[!NOTE]
We handle two edge cases right at the top. If k === 0 (she stops instantly) or n >= k + maxPts (even if she draws the maximum possible number on her last turn, she can't exceed n), the probability is a guaranteed 1.0.

TypeScript / JavaScript

function new21Game(n: number, k: number, maxPts: number): number {
    // Edge cases where she is guaranteed to win
    if (k === 0 || n >= k + maxPts) return 1.0;

    const dp = new Float64Array(n + 1);
    dp[0] = 1.0;
    
    let Wsum = 1.0;
    let probability = 0.0;

    for (let i = 1; i <= n; i++) {
        // Calculate the current probability using the sliding window
        dp[i] = Wsum / maxPts;

        // If she can still draw, add current probability to the window
        if (i < k) {
            Wsum += dp[i];
        } else {
            // If she stops, this probability goes directly into our final answer
            probability += dp[i];
        }

        // Slide the window: remove the oldest probability if it was added
        if (i - maxPts >= 0 && i - maxPts < k) {
            Wsum -= dp[i - maxPts];
        }
    }

    return probability;
}

Python 3

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts:
            return 1.0
            
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        
        Wsum = 1.0
        probability = 0.0
        
        for i in range(1, n + 1):
            dp[i] = Wsum / maxPts
            
            if i < k:
                Wsum += dp[i]
            else:
                probability += dp[i]
                
            if i - maxPts >= 0 and i - maxPts < k:
                Wsum -= dp[i - maxPts]
                
        return probability

Java

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts) {
            return 1.0;
        }

        double[] dp = new double[n + 1];
        dp[0] = 1.0;
        
        double Wsum = 1.0;
        double probability = 0.0;

        for (int i = 1; i <= n; i++) {
            dp[i] = Wsum / maxPts;
            
            if (i < k) {
                Wsum += dp[i];
            } else {
                probability += dp[i];
            }
            
            if (i - maxPts >= 0 && i - maxPts < k) {
                Wsum -= dp[i - maxPts];
            }
        }

        return probability;
    }
}

Complexity Analysis

• Time Complexity: O(N). We execute a single for loop from $1$ up to $n$. Inside the loop, maintaining the Wsum (adding one value, subtracting one value) takes strictly constant $O(1)$ time.
• Space Complexity: O(N). We allocate an array dp of size n + 1 to store the probability of reaching every possible score.

Summary & Key Takeaways

1. Look-back Dependency: Probability DP problems often require looking back at the last $X$ states.
2. Conveyor Belt Optimization: You can heavily optimize these look-backs using a sliding window (maintaining a running sum).
3. Stopping Condition (k): Pay close attention to the stopping condition. You only add states to your running sum if the game rules allow you to continue drawing from that state.

Stay sharp for coding assessments and final exams! Use our free academic tools, including the GPA to Percentage Calculator, to check your academic stats and keep your records in order.