LeetCode 837: New 21 Game Solution
Master LeetCode problem 837 (New 21 Game), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
837. New 21 Game
Problem Explanation
Explanation
To solve this problem, we can use dynamic programming. We will iterate backwards starting from point k, calculating the probability of having n or fewer points at each step. At each point, the probability of having n or fewer points is the sum of the probabilities of reaching n or fewer points in the next maxPts draws, divided by maxPts. We will store these probabilities in an array and return the probability at the starting point 0.
- Time complexity: O(n * maxPts)
- Space complexity: O(n)
Solution Code
class Solution {
public double new21Game(int n, int k, int maxPts) {
double[] dp = new double[n + maxPts + 1];
double sum = 0;
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
sum += dp[i];
}
for (int i = k - 1; i >= 0; i--) {
dp[i] = sum / maxPts;
sum += dp[i] - dp[i + maxPts];
}
return dp[0];
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 837 (New 21 Game)?
This page provides optimized solutions for LeetCode problem 837 (New 21 Game) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 837 (New 21 Game)?
The time complexity for LeetCode 837 (New 21 Game) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 837 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 837 in Java, C++, or Python.