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.
Example 1
Input
maxChoosableInteger = 10, desiredTotal = 11Output
falseNo matter which integer the first player chooses, the second player can respond optimally to reach or exceed the desired total first.
Example 2
Input
maxChoosableInteger = 10, desiredTotal = 0Output
trueThe desired total is already reached, so the first player can force a win immediately.
Constraints
- 1 <= maxChoosableInteger <= 20
- 0 <= desiredTotal <= 300
Asked at 4 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.