#464

Can I Win

expert · 1115 · lc medium +32 · verified · 31% accepted · 2,827 likes · top 8%

⚑ Bitmask DP / State Compression ⚑ Game Theory (Nim / Sprague-Grundy)

Description

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

Code

1

2

3

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: