bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium1-D Dynamic ProgrammingLC 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, 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-5 of the actual answer are considered accepted.

Asked at 3 companies
AppleGoogleUber
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode