bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium2-D Dynamic ProgrammingLC 464

Can I Win

In the "100 game " two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100. Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Asked at 2 companies
GoogleLinkedin
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