algoadvance

Leetcode 837. New 21 Game

Problem Statement

Leetcode Problem 837: New 21 Game

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, W], where each draw is independent and the probability of getting any integer within the range [1, W] is equal. Alice stops drawing numbers when she gets K or more points. Alice wins if her points are anywhere from K to N inclusive.

Given the integers N, K, and W, return the probability that Alice wins the game.

Clarifying Questions

  1. Can points exceed N before reaching K?
    • No, Alice stops drawing if the points reach or exceed K.
  2. What limits do the input values have?
    • 0 ≤ K ≤ N ≤ 10^4 and 1 ≤ W ≤ 10^4.
  3. Is there a minimum value for K where Alice starts drawing points?
    • Yes, Alice starts drawing points while she has less than K points.
  4. Do points reset if Alice decides to stop drawing?
    • No, Alice stops once she reaches or exceeds K points.

Strategy

  1. Dynamic Programming Approach:
    • We’ll use a dynamic programming (DP) array dp where dp[i] represents the probability of having exactly i points.
  2. Initialization:
    • dp[0] is 1 because Alice starts with 0 points.
  3. Filling DP Array:
    • For each point value from 0 to K-1, calculate the probabilities for every future point Alice could get by drawing 1 to W points.
  4. Summation:
    • For each point i from K to N, sum probabilities from dp[i] to get the final result.
  5. Sliding Window Optimization:
    • Use a sliding window to maintain a running sum of probabilities to avoid recalculating sums repeatedly.

Code

public class Solution {
    public double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) {
            return 1.0;
        }
        
        double[] dp = new double[N + 1];
        double sum = 1.0;  // This will store the sum of probabilities in the window
        dp[0] = 1.0;
        double result = 0.0;
        
        for (int i = 1; i <= N; i++) {
            dp[i] = sum / W;
            if (i < K) {
                sum += dp[i];
            } else {
                result += dp[i];
            }
            if (i - W >= 0) {
                sum -= dp[i - W];
            }
        }
        
        return result;
    }
}

Time Complexity

This approach ensures we efficiently calculate the probability of Alice winning the game with the given constraints.

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