How do you solve New 21 Game on LeetCode?

New 21 Game (LeetCode #837) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding the probability distribution of scores is crucial.

What is the brute force solution for New 21 Game?

The brute force approach for New 21 Game is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we simulate every possible way Alice can draw cards until she reaches or exceeds k points. We count how many of these outcomes result in her having n or fewer points. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve New 21 Game?

New 21 Game uses the following concepts: Math, Dynamic Programming, Sliding Window, Probability and Statistics. The recommended patterns to study are: Dynamic Programming, Sliding Window.

What are the interview tips for New 21 Game?

Always clarify the problem constraints and edge cases before diving into coding. Explain your thought process and approach clearly to the interviewer. Practice writing clean and efficient code, as readability matters in interviews.

What are common mistakes when solving New 21 Game?

Forgetting to handle edge cases like k = 0 or n >= k. Not properly managing the sliding window sum in the optimal approach.

#837

New 21 Game

Medium

MathDynamic ProgrammingSliding WindowProbability and StatisticsDynamic ProgrammingSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to keep track of the probabilities of reaching each score efficiently, leveraging the sliding window technique to maintain a running total of probabilities.

⚙️

Algorithm

3 steps

1Step 1: Initialize a dp array where dp[i] represents the probability of reaching exactly i points.
2Step 2: Use a sliding window to keep track of the sum of probabilities for the last maxPts scores.
3Step 3: Update the dp array iteratively until reaching n points, ensuring to adjust the total sum as scores exceed maxPts.

solution.py13 lines

1def new21Game(n, k, maxPts):
2    if k == 0 or n >= k:
3        return 1.0
4    dp = [0.0] * (n + 1)
5    dp[0] = 1.0
6    total = 1.0
7    for i in range(1, n + 1):
8        dp[i] = total / maxPts
9        if i < k:
10            total += dp[i]
11        if i - maxPts >= 0:
12            total -= dp[i - maxPts]
13    return sum(dp[:n + 1])

ℹ

Complexity note: The time complexity is O(n) because we iterate through each score up to n once, and the space complexity is O(n) due to the dp array.

1Understanding the probability distribution of scores is crucial.
2Dynamic programming can simplify complex recursive problems by storing intermediate results.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.