algoadvance

Leetcode 837. New 21 Game

Problem Statement

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 are uniformly distributed.

Alice stops drawing numbers when she gets k or more points. Return the probability that Alice has n or fewer points.

Clarifying Questions

  1. Range of n, k, and maxPts:
    • Are n, k, and maxPts within the range of typical constraints such as 0 ≤ k ≤ n ≤ 10^4 and 1 ≤ maxPts ≤ 10^4?
  2. Edge Cases:
    • What if k is 0? In this case, Alice doesn’t draw any cards, and the probability will depend on whether 0 ≤ n.
    • What if maxPts is 1? It may reduce the problem to a simpler scenario.

Strategy

Dynamic Programming Approach

  1. Problem Insight:
    • We need to track the probability of Alice having specific points from 0 to n.
    • The probability of reaching a state depends on previous states due to the uniformly distributed random drawing.
  2. Dynamic Programming Setup:
    • Let dp[i] be the probability of having i points after some number of draws.
    • Initialize dp[0] = 1.0 because we start with 0 points.
  3. Sliding Window Sum:
    • Use a sliding window sum to maintain the sum of probabilities of the last maxPts scores, reducing the complexity of computing the sum repeatedly.
  4. Transition:
    • For i from 1 to n, dp[i] is computed based on the sliding window sum.
    • If i is less than k, update the sliding window.
  5. Result Calculation:
    • Sum up the probabilities of getting i points where k ≤ i ≤ n.

Code Implementation

#include <vector>
using namespace std;

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts) return 1.0;

        vector<double> dp(n + 1);
        dp[0] = 1.0;
        double windowSum = 1.0;
        double result = 0.0;

        for (int i = 1; i <= n; ++i) {
            dp[i] = windowSum / maxPts;
            if (i < k) {
                windowSum += dp[i];
            } else {
                result += dp[i];
            }
            if (i >= maxPts) {
                windowSum -= dp[i - maxPts];
            }
        }

        return result;
    }
};

Time Complexity

This approach effectively computes the probability that Alice’s score is less than or equal to n after stopping the draws using a dynamic programming approach combined with sliding window technique.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI