New 21 Game - Practice Coding Problems

New 21 Game - Problem

Alice plays a game loosely based on the card game 21. She 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⁻⁵ of the actual answer are considered accepted.

Input & Output

Example 1 — Basic Case

$ Input: n = 21, k = 17, maxPts = 10

› Output: 0.73278

💡 Note: Alice draws until reaching 17+ points. She needs to end with ≤21 points. Most outcomes from 17-26 points are ≤21, giving high probability.

Example 2 — Edge Case

$ Input: n = 6, k = 1, maxPts = 10

› Output: 0.60000

💡 Note: Alice stops after first draw (≥1 point). Draws 1-6 are valid (6 outcomes), draws 7-10 exceed n (4 outcomes). Probability = 6/10 = 0.6.

Example 3 — Guaranteed Win

$ Input: n = 21, k = 17, maxPts = 3

› Output: 1.00000

💡 Note: From any score 14-16, Alice draws 1-3 points, reaching 17-19. All outcomes ≤21, so probability is 1.0.

Constraints

0 ≤ k ≤ n ≤ 10⁴
1 ≤ maxPts ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Game Rules

Alice draws 1-maxPts points while score < k

Stop Condition

Game ends when score ≥ k

Win Condition

Calculate P(final score ≤ n)

Key Takeaway

🎯 Key Insight: Use dynamic programming to calculate probability distribution, optimizing with sliding window for O(n + k) complexity

Asked in

G Google 15 a Amazon 8 M Microsoft 6

The key insight is that Alice stops drawing when reaching k points, so we need to calculate the probability distribution of final scores. The optimal sliding window DP approach maintains a running sum of transition probabilities, achieving O(n + k) time complexity instead of O(k × maxPts).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window DP Optimization	O(n + k)	O(n + k)	Optimize DP transitions using sliding window sum
Recursive Simulation	O(maxPts^k)	O(k)	Recursively simulate all possible game paths
Memoized Recursion	O(n × maxPts)	O(n + k)	Add memoization to avoid recalculating same scores
Bottom-Up Dynamic Programming	O(k × maxPts)	O(n + k)	Build probabilities iteratively from score 0 to k-1

Sliding Window DP Optimization — Algorithm Steps

Initialize dp[0] = 1.0 and sliding window sum
For each score, add current probability to window
Calculate next probability using window sum / maxPts
Update window by removing old values and adding new ones

Visualization

Tap to expand

Step-by-Step Walkthrough

Window Sum

Maintain sum of last maxPts DP values

O(1) Transition

New probability = windowSum / maxPts

Update Window

Add new value, remove old value from sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

double solution(int n, int k, int maxPts) {
    if (k == 0) {
        return n >= 0 ? 1.0 : 0.0;
    }
    if (k >= n) {
        return 1.0;
    }
    
    // dp[i] = probability of reaching score i
    double* dp = (double*)calloc(n + 1, sizeof(double));
    dp[0] = 1.0;
    
    // Sliding window sum for efficient transitions
    double windowSum = 1.0;
    
    for (int i = 1; i <= n; i++) {
        if (i <= k) {
            // Still drawing - use window sum
            dp[i] = windowSum / maxPts;
        } else {
            // Game ended - no new probability
            dp[i] = 0.0;
        }
        
        // Update sliding window
        if (i < k) {
            windowSum += dp[i];
        }
        if (i >= maxPts) {
            windowSum -= dp[i - maxPts];
        }
    }
    
    // Sum probabilities for scores k to n
    double result = 0.0;
    for (int i = k; i <= n; i++) {
        result += dp[i];
    }
    
    free(dp);
    return result;
}

int main() {
    int n, k, maxPts;
    scanf("%d", &n);
    scanf("%d", &k);
    scanf("%d", &maxPts);
    
    double result = solution(n, k, maxPts);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k)

Each score is processed once with O(1) sliding window operations

✓ Linear Growth

Space Complexity

O(n + k)

DP array stores probabilities for relevant score range

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window DP Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler