MediumNo. 0837
New 21 Game — LeetCode 837 Python Solution
- Pattern
- Sliding Window
- Topics
- Math, Dynamic Programming, Sliding Window, Probability and Statistics
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- Input
- n = 10, k = 1, maxPts = 10
- Output
- 1.00000
- Explanation
- Alice gets a single card, then stops.
Python solution
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
@cache
def dfs(i: int) -> float:
if i >= k:
return int(i <= n)
if i == k - 1:
return min(n - k + 1, maxPts) / maxPts
return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts
return dfs(0)Complexity
- Time
- O(n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 837. New 21 Game is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2110 | Number of Smooth Descent Periods of a Stock | Medium |
| 0470 | Implement Rand10() Using Rand7() | Medium |
| 1040 | Moving Stones Until Consecutive II | Medium |
| 1093 | Statistics from a Large Sample | Medium |
| 1610 | Maximum Number of Visible Points | Hard |
| 2269 | Find the K-Beauty of a Number | Easy |
Frequently asked questions
- How hard is LeetCode 837. New 21 Game?
LeetCode 837. New 21 Game is rated Medium on LeetCode.
- What topics does LeetCode 837. New 21 Game cover?
LeetCode 837. New 21 Game is tagged Math, Dynamic Programming, Sliding Window and Probability and Statistics on LeetCode.