Give it 2 hours . TRY it yourself for logic building from scratch ! ✔🐱‍🏍🙌
Intuition\n##### Build-up for the game :-\n\nIn this game, Alice starts with 0 points and draws numbers randomly. She wants to know the chance of having n or fe
# Intuition\n##### Build-up for the game :-\n\nIn this game, Alice starts with 0 points and draws numbers randomly. She wants to know the chance of having `n` or fewer points at the end.\n\nTo figure this out, we can use a trick called "counting." We start counting from 0 and keep track of the chance of having each number of points. \n\nWe use a list to remember the chances. At the beginning, the chance of having 0 points is 100% or 1.0. Then we look at the next number, 1, and think about how we can get there. We can get to 1 point by drawing a number from 1 to `maxPts`. We calculate the chances of each of those possibilities and add them up. \n\nNext, we move on to the number 2 and do the same thing. We consider all the ways to get to 2 points, based on the chances we already calculated for the previous numbers.\n\nWe keep doing this for each number up to `n`, using the chances we already know to figure out the chances for the next number.\n\nFinally, we add up all the chances from `k` to `n` to find the overall chance of having `n` or fewer points.\n\nSo, in simple terms, we\'re just counting and keeping track of the chances of having different numbers of points. We use the chances we already calculated to find the chances for the next numbers. By adding up all the chances, we get the answer Alice is looking for.\n\n----\n##### More Intuition in technical terms now :- \n\nIn this game, Alice starts with 0 points and draws numbers randomly until she reaches a certain number of points called `k`. We want to know the probability of Alice having `n` or fewer points at the end of the game.\n\nTo solve this problem, we can use a technique called Dynamic Programming, or DP for short. DP is like a special way of solving problems where we break down a big problem into smaller, easier-to-solve subproblems.\n\nIn this case, we can think of the problem like a puzzle. We start with the smallest subproblem: what is the probability of having 0 points? Since Alice starts with 0 points, the probability is 100% or 1.0.\n\nThen, we move on to the next subproblem: what is the probability of having 1 point? To solve this, we look at all the ways Alice can get 1 point. She can draw a number from 1 to `maxPts`, so we need to consider all those possibilities and calculate the probabilities. Once we know the probabilities of having 0 and 1 point, we can calculate the probability of having 2 points by adding up the probabilities of getting to 2 from the previous points (0 and 1).\n\nWe keep doing this for all the points up to `n`. Each time, we use the probabilities we already calculated for the previous points to calculate the probability for the current point. This is why we use a list or array called `dp` to store the probabilities. `dp` stands for "dynamic programming".\n\nBy building up the probabilities step by step, using the probabilities we already know, we can finally find the probability of having `n` or fewer points.\n\nSo, in summary, we use dynamic programming (DP) to solve this problem because it helps us break down the big problem into smaller, easier-to-solve subproblems. We calculate the probabilities for each point by using the probabilities we already calculated for the previous points. This way, we can find the final probability we\'re looking for.\n\n----\n##### Maths :-\n\nCertainly! Let\'s denote the probability that Alice has exactly `i` points as `P[i]`. We want to calculate the probability that Alice has `n` or fewer points, which can be expressed as:\n\n> P(n) = P[0] + P[1] + P[2] + ... + P[n]\n\nTo calculate `P[i]`, we can use dynamic programming and break it down into subproblems. Here\'s the recursive equation:\n\n> P[i] = (P[i-1] + P[i-2] + ... + P[i-maxPts]) / maxPts\n\nThe above equation states that the probability of having `i` points is equal to the sum of probabilities of reaching the current point from the previous `maxPts` points, divided by `maxPts`. This is because in each draw, Alice gains an integer number of points randomly from the range [1, maxPts] with equal probabilities.\n\nTo calculate `P[i]`, we iterate from 1 to `n` and use the above equation to fill in the probabilities in a dynamic programming array or list. We initialize `P[0] = 1` since Alice starts with 0 points. Then, we calculate `P[1]` using the equation, followed by `P[2]`, and so on, until we reach `P[n]`. Finally, we sum up the probabilities from `P[k]` to `P[n]` to obtain the desired probability.\n\nBy using dynamic programming, we avoid recalculating the same probabilities multiple times, leading to an efficient solution to the problem.\n\n----\n##### Intuition for the code :-\nThe given code calculates the probability that Alice will have `n` or fewer points in the game, where Alice starts with 0 points and draws numbers randomly until she reaches `k` or more points.\n\nHere\'s the intuition behind the code:\n\n1. First, the code checks for a special case where `k` is 0 or `n` is greater than or equal to `k + maxPts`. In these cases, it means that Alice is guaranteed to have `n` or fewer points, so the probability is 1.0. The code returns 1.0 in these cases.\n\n2. If the special cases don\'t apply, the code proceeds to calculate the probability using dynamic programming.\n\n3. A list `dp` is initialized with `n + 1` elements, representing the probabilities of having each number of points from 0 to `n`. All elements are initially set to 0.0, except for `dp[0]`, which is set to 1.0 since Alice starts with 0 points.\n\n4. The loop iterates from 1 to `n`, and for each index `i`, it calculates the probability `dp[i]` of having `i` or fewer points.\n\n5. The probability `dp[i]` is calculated by summing the probabilities of getting to `i` from the previous points. The probability of getting to `i` is equal to the sum of the probabilities of getting to `i - 1`, `i - 2`, ..., `i - maxPts`, divided by `maxPts`.\n\n6. The variable `_sum` is used to keep track of the cumulative sum of probabilities. It is initialized to 1.0 since `dp[0] = 1.0`.\n\n7. Within the loop, if `i` is less than `k`, the current probability `dp[i]` is added to `_sum` to update the cumulative sum.\n\n8. If `i - maxPts` is greater than or equal to 0, it means that the window of the previous `maxPts` probabilities has shifted, so the probability at `i - maxPts` is subtracted from `_sum` to keep the sliding window of size `maxPts` in the cumulative sum.\n\n9. After the loop, the final probability of winning is calculated by summing the probabilities starting from index `k` to the end of the list (`sum(dp[k:])`) since Alice stops drawing numbers when she reaches `k` or more points.\n\nThe code uses dynamic programming to efficiently calculate the probabilities by reusing the results of previous calculations. By iterating through the indices and updating the probabilities based on the previous results, it builds up the probability distribution for the desired range of points. \n\n# Approach\n\nIn this version, the circular buffer is replaced with a simple list `dp`, which stores the probabilities.\n\nHere\'s an explanation of the changes:\n\n1. The `if` condition `n >= k + maxPts` is used to determine whether the probability of winning is guaranteed to be 1. If true, the function directly returns 1.0.\n\n2. Instead of using a circular buffer, a regular list `dp` of size `n + 1` is initialized with all elements set to 0.0. The element `dp[0]` is set to 1.0 to represent the initial probability.\n\n3. The variable `_sum` is used to keep track of the cumulative sum of probabilities. It is initialized to 1.0.\n\n4. The loop iterates from 1 to `n`, and at each iteration, the probability for the current index `i` is calculated as `_sum / maxPts`. The `_sum` is divided by `maxPts` because there are `maxPts` possible outcomes, each with an equal probability of occurring.\n\n5. If `i` is less than `k`, the current probability `dp[i]` is added to `_sum` to update the cumulative sum.\n\n6. If `i - maxPts` is greater than or equal to 0, the probability `dp[i - maxPts]` is subtracted from `_sum` to keep the sliding window of size `maxPts` in the cumulative sum.\n\n7. After the loop, the final probability of winning is calculated by summing the probabilities starting from index `k` to the end of the list (`sum(dp[k:])`) and returned.\n\nThis version eliminates the need for a circular buffer and simplifies the code while maintaining efficiency.\n\n# Complexity\n- **Time complexity** : $$O(n)$$, here n is the value given as input.\n- **Space complexity** : $$O(n)$$, w here n is the value given as    input. This is because the code uses a list `dp` of size `n + 1` to store the probabilities for each number of points from 0 to n.\n\nThe loop that iterates from 1 to n has a time complexity of $$O(n)$$. Within the loop, the calculations involve accessing elements of the `dp` list, which has a constant time complexity. Overall, the time complexity of the code is determined by the loop, resulting in $$O(n)$$.\n\nSimilarly, the space complexity is determined by the `dp` list, which has a size of n + 1. Therefore, the space complexity of the code is $$O(n)$$.\n\n# Code\n```\nclass Solution:\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        \'\'\'\n        if k == 0 or n >= k + maxPts:\n            return 1\n        \n        windowSum = 1\n        probability = 0\n        \n        dp = [0] * (n + 1)\n        dp[0] = 1\n        \n        for i in range(1, n + 1):\n            dp[i] = windowSum / maxPts\n            \n            if i < k:\n                windowSum += dp[i]\n            else:\n                probability += dp[i]\n            \n            if i >= maxPts:\n                windowSum -= dp[i - maxPts]\n        \n        return probability\n        \'\'\'\n\n# MLE\n\'\'\'\nclass CircularBuffer:\n    def __init__(self, min_size):\n        self.data = [None] * (1 << self.bit_len(min_size))\n        self.mask = len(self.data) - 1\n\n    @staticmethod\n    def bit_len(min_size):\n        return 32 - min_size.bit_length()\n\n    def __getitem__(self, index):\n        return self.data[index & self.mask]\n\n    def __setitem__(self, index, value):\n        self.data[index & self.mask] = value\n\n    def capacity(self):\n        return len(self.data)\n\n    def get_mask(self):\n        return self.mask\n\nclass Solution:\n    def new21Game(self, n, k, maxPts):\n        if k == 0 or n - k + 1 >= maxPts:\n            return 1.0\n\n        kFactor = 1.0 / maxPts\n        if maxPts + 1 >= n:\n            return pow(1 + kFactor, k - 1) / maxPts * (n - k + 1)\n\n        dp = CircularBuffer(maxPts + 1)\n        dp[0] = 1.0\n        _sum = 1.0\n        for i in range(1, k):\n            dp[i] = _sum * kFactor\n            _sum += dp[i] - dp[i - maxPts]\n\n        answer = 0.0\n        for i in range(k, n + 1):\n            answer += _sum * kFactor\n            _sum -= dp[i - maxPts]\n\n        return answer\n\'\'\'\n\n# Efficient Solution:-\nclass Solution:\n    def new21Game(self, n, k, maxPts):\n        if k == 0 or n >= k + maxPts:\n            return 1.0\n\n        dp = [0.0] * (n + 1)\n        dp[0] = 1.0\n        _sum = 1.0\n        for i in range(1, n + 1):\n            dp[i] = _sum / maxPts\n            if i < k:\n                _sum += dp[i]\n            if i - maxPts >= 0:\n                _sum -= dp[i - maxPts]\n\n        return sum(dp[k:])\n\n```
['Math', 'Dynamic Programming', 'Sliding Window', 'Probability and Statistics', 'Python3']