✅ 0ms | ✨ O(N) O(maxPts) | 🏆 Most Efficient Solution | 👍 Simplest Code with Circular Buffer
Intuition\n Describe your first thoughts on how to solve this problem. \n## Probability Analysis\nWhen Alice has x points and she tries next round, the probabil
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n## Probability Analysis\nWhen Alice has x points and she tries next round, the probability of getting y points that round is:\n\n$$P(x \\rightarrow y | x) = 1 / L$$ if $x < k$ and $y \\in [x + 1, x + L]$\nwhere $L$ is `maxPts` and $x \\rightarrow y$ means the event of getting x points first then immediately getting y points after.\n\nUsing the conditional probability formula we have:\n\n$$P(x \\rightarrow y) = P(x \\rightarrow y | x) * P(x)$$\n\nIf we think this backwards, then the probability of getting x points is:\n\n$$\nP(x) = \\sum_{i= 1}^L P((x - i) \\rightarrow x)\n = \\sum_{i= 1}^L P((x - i) \\rightarrow x | x - i) * P(x - i) \\\\\n = \\sum_{i=1}^L \\frac{1}{L} P(x - i)\n = \\frac{1}{L} \\sum_{i=1}^L P(x - i)\n$$\nThe above formula assumes $x \\le k$ and uses the convention $P(x) = 0$ for $x < 0$ to simply things.\n\nBecause Alice stops playing once she got $k$ or more points, we only need to modify the above recursive relation slightly:\n\n$$P(x) = \\frac{1}{L} \\sum_{i=x - k + 1}^L P(x - i)$$ for $x \\ge k$\n\n## Dynamic Programming and Sliding Window\nWe can easily calculate each $P(x)$ using simple **dynamic programming** and a **sliding window** tech.\n\nFor example, when $L = 4$:\n$$P(27) = \\frac{1}{4} (P(26) + P(25) + P(24) + P(23)) = S_{26}/4$$\nThen next we update our window sum $S$ by:\n$$S_{27} = S_{26} + P(27) - P(23) $$\nand so on.\n\nFor the case when $x \\ge k$ the sliding window shrinks only.\n\n## Special Cases\n\n### Stops at Zero\nWhen $k = 0$ there is no round at all and we simply return `1` since we are promised that $n \\ge k$.\n\n### Sliding Window too Small\nWhen $k - 1 + L <= n$, there is no way for Alice to get points more than $n$ directly from $x < k$. In this case we simply return `1` and no further calculation needed.\n\n### Sliding Window too Big\nWhen $1 + L >= n$\nIn this case the sliding window\'s "tail" is negative index. While the **Circular Buffer** optimization below handles negative index well and this special case will work just fine, we can nevertheless use a more efficient algorithm for this special case.\n\nSimplify the summation boundary of our previous formula:\n\n$$\nP(x) = \\frac{1}{L} \\sum_{i=0}^{x - 1} P(i) = \\frac{1}{L} S_{x-1}\n\\Rightarrow S_x = S_{x - 1} + P(x) = (1 + \\frac{1}{L}) S_{x - 1}\n$$\nwhere $1 \\le x \\le k$\n\nIf we define $\\alpha = (1 + \\frac{1}{L})$ we get a nice result for $S_x$:\n$$S_x = \\alpha^{x - 1}$$ for $x \\le k$\n\nand then:\n$$P(x) = \\frac{1}{L} S_{k-1} = \\frac{1}{L} \\alpha^{k-1}$$ for $x \\ge k$\n\nNotice that the probability we are looking for is the sum of these between $[k, n]$ and since they are *all the same*, we simply get:\n$$P = \\frac{1}{L} \\alpha^{k-1} (n - k + 1)$$\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe use a circular buffer to store the last $L + 1$ probability data.\nWe use a sliding window to keep updating the last one.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N)$$ normally.\n$$\\Theta(1)$$ for the first two special cases.\n$$\\Theta(\\log k)$$ for the last case.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(L)$$ normally (in this case we have $L \\le N$).\n$$\\Theta(1)$$ for the first two special cases.\n$$\\Theta(1)$$ for the last case (in this case when $L > N$).\nwhere $L$ is the `maxPts`\n\n\n# Code\n```\n\ntemplate <typename T>\nclass CircularBuffer {\n public:\n  explicit CircularBuffer(int min_size) : data_(1 << BitLen(min_size)), mask_(data_.size() - 1) {}\n\n  static constexpr int BitLen(int min_size) {\n    return 32 - __builtin_clz(min_size);\n  }\n\n  T& operator[](int index) {\n    return data_[index & mask_];\n  }\n\n  const T& operator[](int index) const {\n    return data_[index & mask_];\n  }\n\n  int Capacity() const {\n    return data_.size();\n  }\n\n  int mask() const { return mask_; }\n\n private:\n  std::vector<T> data_;\n  const uint mask_;\n};\n\nclass Solution {\n public:\n  double new21Game(int n, int k, int maxPts) {\n    if (k == 0 || n - k + 1 >= maxPts) {\n      return 1;\n    }\n    const double kFactor = 1.0 / maxPts;\n    if (maxPts + 1 >= n) {\n      return std::pow(1 + kFactor, k - 1) / maxPts * (n - k + 1);\n    }\n\n    CircularBuffer<double> dp(maxPts + 1);\n    dp[0] = 1;\n    double sum = 1;\n    for (int i = 1; i < k; ++i) {\n      dp[i] = sum * kFactor;\n      sum += dp[i] - dp[i - maxPts];\n    }\n    double answer = 0;\n    for (int i = k; i <= n; ++i) {\n      answer += sum * kFactor;\n      sum -= dp[i - maxPts];\n    }\n    return answer;\n  }\n};\n```
['Math', 'Dynamic Programming', 'Sliding Window', 'Probability and Statistics', 'C++']