Medium
Quiz
#464 Can I Win
APPROACH
Two players alternate picking distinct integers from 1 to maxChoosableInteger (each integer may be chosen at most once), adding each pick to a shared running total. The player who first causes the total to reach or exceed desiredTotal wins.
With both players playing optimally, return true if the first player can guarantee a win, otherwise false.
Example 1:
Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
Example 2:
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
Example 3:
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
1 of 4
1:00
What is the optimal approach for this problem?