We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

New 21 Game

Number: 867

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Alice starts with 0 points and keeps drawing numbers from 1 to maxPts uniformly at random until she reaches at least k points. Once she reaches k or more points, she stops drawing. The problem asks for the probability that Alice ends up with n or fewer points.

Key Insights

  • If k is 0, Alice never draws a card, so the answer is 1.
  • If n is large enough (n >= k - 1 + maxPts), Alice will always win.
  • Use dynamic programming to compute the probability of reaching every score from 0 to n.
  • Use a sliding window sum to efficiently compute the probability recurrence relation.
  • The state transition relates dp[x] to the sum of probabilities dp[x - 1] ... dp[x - maxPts] divided by maxPts.

Space and Time Complexity

Time Complexity: O(n), because we calculate each dp state at most once. Space Complexity: O(n), for storing the dp array.

Solution

We solve this problem using dynamic programming with a sliding window approach:

  1. Create an array dp where dp[i] represents the probability of reaching exactly i points.
  2. Base case: dp[0] = 1.0 (starting with 0 points).
  3. Use a sliding window sum to maintain the sum of dp values for states from i - maxPts to i - 1.
  4. For each score i from 1 to n:
    • The probability dp[i] is the average of the probabilities in the window.
    • If i is less than k, add dp[i] to the window sum.
    • If i - maxPts is within range, subtract dp[i - maxPts] from the window sum.
  5. The final answer is the sum of dp[i] for i from k to n, as these are the terminal states where Alice stops.

Code Solutions

# Python solution for New 21 Game
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        # Edge case: If k is 0 then Alice doesn't draw any card, always count as 1.
        if k == 0:
            return 1.0
        
        # dp[i] will represent the probability of reaching exactly i points.
        dp = [0.0] * (n + 1)
        dp[0] = 1.0  # start with 0 points, probability 1
        
        # W is the cumulative probability for states that can transition into the current state.
        w = 1.0
        result = 0.0
        
        # Calculate probabilities for each score from 1 to n.
        for i in range(1, n + 1):
            dp[i] = w / maxPts
            # Only add probabilities for states less than k to the window because game ends when score >= k.
            if i < k:
                w += dp[i]
            else:
                # For i >= k, these states represent a terminal state where Alice stops.
                result += dp[i]
            # If the window has exceeded the size maxPts, subtract the oldest probability.
            if i - maxPts >= 0:
                w -= dp[i - maxPts]
        
        return result

# Example usage:
# solution = Solution()
# print(solution.new21Game(21, 17, 10))
← Back to All Questions