Is New 21 Game easy or hard?

New 21 Game is considered a medium difficulty problem. The main challenge is recognizing the probabilistic DP recurrence and optimizing it with a sliding window to avoid O(n * maxPts) transitions.

New 21 Game Python/Java solution

Implement a DP array where dp[i] stores the probability of reaching score i. Maintain a sliding window sum of valid previous states and update it while iterating. The same logic works across Python, Java, C++, C#, and JavaScript implementations.

How to solve New 21 Game in O(n)?

Maintain a sliding window sum of the previous maxPts probabilities that correspond to scores below k. Compute dp[i] = windowSum / maxPts and update the window as you iterate forward. Each index is processed once, giving linear time complexity.

What is the best approach for New 21 Game?

The best approach uses dynamic programming with a sliding window. Define dp[i] as the probability of reaching score i and maintain a running sum of the last maxPts states that can still draw cards. This reduces the transition cost from O(maxPts) to O(1) per state, giving overall O(n) time complexity.

Is New 21 Game asked at Google/Amazon/Meta?

New 21 Game appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests probability modeling and dynamic programming optimization. The sliding window optimization is typically the expected interview solution.

What data structure is used in New 21 Game?

The core data structure is a dynamic programming array that stores probabilities for each possible score. A running sliding window sum is maintained to efficiently compute transitions from the previous maxPts states.

What is the time complexity of New 21 Game?

The optimized solution runs in O(n) time and O(n) space using dynamic programming with a sliding window. A naive DP implementation that recomputes sums for each state takes O(n * maxPts) time.

Description Solution Video 19:03

837. New 21 Game

Medium52.0% acceptance5 companies

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.

Example 1:

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

Example 2:

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:

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

Constraints:

0 <= k <= n <= 10⁴
1 <= maxPts <= 10⁴

Asked at 5 companies

Google Amazon Microsoft Bloomberg Meta

Topics

19:03

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

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

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

10
1
10

Input

6
1
10

Input

21
17
10

Your code is saved on this device.Solution