LeetCode 837: New 21 Game

Problem Restatement

Alice starts with 0 points.

While her score is less than k, she keeps drawing a random number from 1 to maxPts.

Each draw is independent, and every number from 1 to maxPts has the same probability.

Alice stops drawing as soon as her score is at least k.

Return the probability that Alice ends with n or fewer points.

Answers within 10^-5 of the correct answer are accepted.

Input and Output

Function shape:

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        ...

Examples

Example 1:

n = 10
k = 1
maxPts = 10

Alice draws exactly once, because after the first draw her score is at least 1.

The draw is between 1 and 10.

Every possible final score is at most 10.

So the answer is:

1.0

Example 2:

n = 6
k = 1
maxPts = 10

Alice draws exactly once.

The final score is one of:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Only 1 through 6 are valid.

So the probability is:

6 / 10 = 0.6

Example 3:

n = 21
k = 17
maxPts = 10

The answer is approximately:

0.73278

First Thought: Recursive Probability

Let:

dp[x]

mean the probability of eventually ending with score at most n, starting from score x.

If x >= k, Alice stops immediately.

So:

dp[x] = 1, if x <= n
dp[x] = 0, if x > n

If x < k, Alice draws a number from 1 to maxPts.

So:

dp[x] = (dp[x + 1] + dp[x + 2] + ... + dp[x + maxPts]) / maxPts

This is correct, but computing every sum directly is too slow.

Problem With Direct DP

For every score x, direct DP may sum maxPts future states.

That gives:

O(k * maxPts)

This can be too large.

We need to reuse the sum of nearby DP values.

Key Insight

The recurrence uses a moving window:

dp[x] = average of dp[x + 1] through dp[x + maxPts]

When moving from one x to the next, most of the window stays the same.

So we can maintain a sliding sum instead of recomputing the whole sum.

There is also a useful forward version.

Let:

dp[i]

be the probability that Alice reaches exactly score i.

Initially:

dp[0] = 1

A score i can be reached from previous scores:

i - 1, i - 2, ..., i - maxPts

but only previous scores less than k can draw again.

So we maintain:

window_sum = sum of probabilities of active previous scores

Then:

dp[i] = window_sum / maxPts

Algorithm

Handle the easy winning case first.

If:

k == 0

Alice never draws, so her score is 0, and the answer is 1.

Also, the maximum possible final score is:

k - 1 + maxPts

because Alice can draw only while her score is at most k - 1, then she may draw up to maxPts.

If:

n >= k - 1 + maxPts

then every possible final score is at most n, so the answer is 1.

Otherwise:

1. Create dp where dp[i] is the probability of reaching score i.
2. Set dp[0] = 1.
3. Set window_sum = 1.
4. For each score i from 1 to n:
   1. Set dp[i] = window_sum / maxPts.
   2. If i < k, add dp[i] to window_sum.
   3. If i - maxPts >= 0, remove dp[i - maxPts] from window_sum.
   4. If i >= k, add dp[i] to the answer.

Walkthrough

Use:

n = 6
k = 1
maxPts = 10

Alice starts at 0.

Since 0 < k, she draws once.

Each result from 1 to 10 has probability:

1 / 10

Valid final scores are:

1, 2, 3, 4, 5, 6

There are 6 valid scores, each with probability 0.1.

So:

answer = 6 * 0.1 = 0.6

The DP computes the same value.

For i = 1 through 6, each dp[i] receives:

dp[0] / 10 = 0.1

Since all these scores are at least k, they are final scores.

The answer becomes:

0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 = 0.6

Correctness

The value dp[i] represents the probability that Alice reaches score i.

The initial state is correct because Alice starts at score 0, so dp[0] = 1.

A score i can be reached only from a previous score j where:

1 <= i - j <= maxPts

and Alice must still be drawing at j, which requires:

j < k

Each active previous score contributes:

dp[j] / maxPts

to dp[i].

The sliding window stores exactly the sum of these active previous probabilities. Therefore, assigning:

dp[i] = window_sum / maxPts

computes the correct probability of reaching score i.

When i < k, Alice may draw again from score i, so dp[i] is added to the active window.

When i >= k, Alice stops at score i, so dp[i] is added to the answer instead.

The window also removes scores more than maxPts behind, because they can no longer reach the current or future score with one draw.

Thus every final score from k through n is counted once, and no non-final or too-large score is counted. The returned sum is exactly the probability that Alice ends with score at most n.

Complexity

Implementation

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k - 1 + maxPts:
            return 1.0

        dp = [0.0] * (n + 1)
        dp[0] = 1.0

        window_sum = 1.0
        answer = 0.0

        for score in range(1, n + 1):
            dp[score] = window_sum / maxPts

            if score < k:
                window_sum += dp[score]
            else:
                answer += dp[score]

            if score - maxPts >= 0:
                window_sum -= dp[score - maxPts]

        return answer

Code Explanation

The early return handles cases where Alice always wins:

if k == 0 or n >= k - 1 + maxPts:
    return 1.0

dp[score] stores the probability of reaching exactly score:

dp = [0.0] * (n + 1)
dp[0] = 1.0

The sliding sum starts with score 0, because Alice can draw from score 0:

window_sum = 1.0

For each score:

dp[score] = window_sum / maxPts

This distributes probability from all active previous scores.

If score < k, Alice can still draw from this score:

window_sum += dp[score]

If score >= k, this is a stopping score:

answer += dp[score]

Finally, remove scores that are too far behind:

if score - maxPts >= 0:
    window_sum -= dp[score - maxPts]

Testing

def almost_equal(a: float, b: float, eps: float = 1e-5) -> bool:
    return abs(a - b) <= eps

def run_tests():
    s = Solution()

    assert almost_equal(s.new21Game(10, 1, 10), 1.0)
    assert almost_equal(s.new21Game(6, 1, 10), 0.6)
    assert almost_equal(s.new21Game(21, 17, 10), 0.73278)
    assert almost_equal(s.new21Game(0, 0, 1), 1.0)
    assert almost_equal(s.new21Game(1, 0, 1), 1.0)
    assert almost_equal(s.new21Game(5, 2, 3), 1.0)

    print("all tests passed")

run_tests()

Test meaning: