Problem

Alice plays the following game, loosely based on the card game “21”.

Alice 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-5 of the actual answer are considered accepted.

Examples

Example 1

1
2
3

Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.

Example 2

1
2
3
4

Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.

Example 3

1
2

Input: n = 21, k = 17, maxPts = 10
Output: 0.73278

Constraints

  • 0 <= k <= n <= 10^4
  • 1 <= maxPts <= 10^4

Solution

Method 1 – Dynamic Programming with Sliding Window

Intuition

We use DP where dp[x] is the probability of getting exactly x points. For each state, the probability is the average of the previous maxPts states. To optimize, we use a sliding window sum.

Approach

  1. If k == 0 or n >= k + maxPts - 1, Alice always wins, return 1.
  2. Initialize dp[0] = 1 and a window sum variable.
  3. For each i from 1 to n:
    • dp[i] = window / maxPts.
    • If i < k, add dp[i] to window.
    • If i - maxPts >= 0, subtract dp[i - maxPts] from window.
  4. The answer is the sum of dp[k] to dp[n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts - 1) return 1.0;
        vector<double> dp(n+1);
        dp[0] = 1.0;
        double window = 1.0, ans = 0.0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = window / maxPts;
            if (i < k) window += dp[i];
            else ans += dp[i];
            if (i - maxPts >= 0) window -= dp[i - maxPts];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func new21Game(n, k, maxPts int) float64 {
    if k == 0 || n >= k+maxPts-1 {
        return 1.0
    }
    dp := make([]float64, n+1)
    dp[0] = 1.0
    window, ans := 1.0, 0.0
    for i := 1; i <= n; i++ {
        dp[i] = window / float64(maxPts)
        if i < k {
            window += dp[i]
        } else {
            ans += dp[i]
        }
        if i-maxPts >= 0 {
            window -= dp[i-maxPts]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts - 1) return 1.0;
        double[] dp = new double[n+1];
        dp[0] = 1.0;
        double window = 1.0, ans = 0.0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = window / maxPts;
            if (i < k) window += dp[i];
            else ans += dp[i];
            if (i - maxPts >= 0) window -= dp[i - maxPts];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun new21Game(n: Int, k: Int, maxPts: Int): Double {
        if (k == 0 || n >= k + maxPts - 1) return 1.0
        val dp = DoubleArray(n+1)
        dp[0] = 1.0
        var window = 1.0
        var ans = 0.0
        for (i in 1..n) {
            dp[i] = window / maxPts
            if (i < k) window += dp[i]
            else ans += dp[i]
            if (i - maxPts >= 0) window -= dp[i - maxPts]
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0
        dp = [0.0] * (n+1)
        dp[0] = 1.0
        window = 1.0
        ans = 0.0
        for i in range(1, n+1):
            dp[i] = window / maxPts
            if i < k:
                window += dp[i]
            else:
                ans += dp[i]
            if i - maxPts >= 0:
                window -= dp[i - maxPts]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
        if k == 0 || n >= k + max_pts - 1 {
            return 1.0;
        }
        let n = n as usize;
        let k = k as usize;
        let max_pts = max_pts as usize;
        let mut dp = vec![0.0; n+1];
        dp[0] = 1.0;
        let mut window = 1.0;
        let mut ans = 0.0;
        for i in 1..=n {
            dp[i] = window / max_pts as f64;
            if i < k {
                window += dp[i];
            } else {
                ans += dp[i];
            }
            if i >= max_pts {
                window -= dp[i - max_pts];
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    new21Game(n: number, k: number, maxPts: number): number {
        if (k === 0 || n >= k + maxPts - 1) return 1.0;
        const dp = Array(n+1).fill(0);
        dp[0] = 1.0;
        let window = 1.0, ans = 0.0;
        for (let i = 1; i <= n; ++i) {
            dp[i] = window / maxPts;
            if (i < k) window += dp[i];
            else ans += dp[i];
            if (i - maxPts >= 0) window -= dp[i - maxPts];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We fill the DP array once.
  • 🧺 Space complexity: O(n) — For the DP array.