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 have equal probabilities.
Alice stops drawing numbers when she gets k or more points.
Return the probability that Alice has n or fewer points.
Answers within 10<sup>-5</sup> of the actual answer are considered accepted.
Link: https://leetcode.com/problems/new-21-game/description/
Problem Explanation with examples:-
Example 1
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Example 2
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
Example 3
Input: n = 21, k = 17, maxPts = 10
Output: 0.73278
Constraints
0 <= k <= n <= 10<sup>4</sup>1 <= maxPts <= 10<sup>4</sup>
Intuition:-
Treating it as a sliding window problem, we can see that the window size is maxPts.
For each index, we have to ensure whether that index can suffice the condition of the problem i.e. it should be less than or equal to n. If it is, then we add 1 to the window sum, else we add 0.
Then we have to find the probability of each index. For that, we have to divide the window sum by maxPts for each index.
Now, we have to find the probability of each index from k-1 to 0. For that, we can use a dictionary to store the probability of each index.
For each index, we have to find the window sum of the next index and subtract the probability of the next index from it. Then we have to add the probability of the current index to it.
We have to do this for each index from k-1 to 0.
Finally, we return the probability of the 0th index.
Solution:-
Check if k is 0. If it is, then return 1.0 as the probability of reaching 0 is 1.
Run a loop from k to k+maxPts. If the index is less than or equal to n, then add 1 to the window sum, else add 0.
Create a dictionary to store the probability of each index.
Run a loop from k-1 to -1 with a step of -1. For each index, find the window sum and divide it by maxPts. Store it in the dictionary.
Initialize variable rem to 0. If i+maxPts is less than or equal to n, then find the probability of i+maxPts from the dictionary and store it in rem. Else, store 1 in rem.
This is checked to keep track of the window size. If the window size is less than maxPts, then we have to add the probability of the next index to the window sum. Else, we have to subtract the probability of the next index from the window sum.
Update the window sum by subtracting rem from it and adding the probability of the current index to it.
Return the probability of the 0th index from the dictionary.
Code:-
JAVA Solution
class Solution {
public double new21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
double wsum = 0;
for (int i = k; i < k + maxPts; i++) {
wsum += (i <= n) ? 1 : 0;
}
Map<Integer, Double> dp = new HashMap<>();
for (int i = k - 1; i >= 0; i--) {
dp.put(i, wsum / maxPts);
double rem = 0;
if (i + maxPts <= n) {
rem = dp.getOrDefault(i + maxPts, 1.0);
}
wsum += (dp.get(i) - rem);
}
return dp.get(0);
}
}
Python Solution
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
if k == 0:
return 1.0
wsum = 0
for i in range(k, k+maxPts):
wsum += 1 if i <= n else 0
dp = {}
for i in range(k-1, -1, -1):
dp[i] = wsum/maxPts
rem = 0
if i+maxPts <= n:
rem = dp.get(i+maxPts,1)
wsum += (dp[i] - rem)
return dp[0]
Complexity Analysis:-
TIME:-
The time complexity of add method is O(k + maxPts), as there are loops iterating from k to k + maxPts - 1 and from k - 1 to 0.
SPACE:-
The space complexity is O(k), as the HashMap dp stores probabilities for each index from k - 1 to 0.