{x}
blog image

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 = 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

 

Constraints:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

Solution Explanation: Can I Win

This problem is a classic game theory problem that can be solved efficiently using dynamic programming with bit manipulation for state representation. The core idea is to explore all possible game states and determine if the first player can force a win.

Understanding the Problem:

Two players take turns choosing numbers from a set {1, 2, ..., maxChoosableInteger} without replacement. The player who first makes the sum of their chosen numbers reach or exceed desiredTotal wins. The question asks whether the first player can win if both players play optimally.

Approach: Memoized Dynamic Programming with Bitmasking

  1. Base Cases:

    • If the sum of all numbers (1 + 2 + ... + maxChoosableInteger) is less than desiredTotal, the first player cannot win, so we return false.
    • If desiredTotal is 0 or less, the first player wins (already at or above the target), so we return true.

  2. State Representation (Bitmasking): We use a bitmask (mask) to represent the state of the game. Each bit in the mask corresponds to a number in the set {1, 2, ..., maxChoosableInteger}. A bit set to 1 indicates the number is already chosen; a bit set to 0 indicates it's available. This allows us to efficiently track which numbers have been selected.

  3. Recursive Function dfs(mask, currentSum):

    • This function recursively explores the game tree.
    • It takes the current bitmask (mask) and the current sum (currentSum) as input.
    • It iterates through all available numbers (numbers with a 0 bit in the mask).
    • For each available number i:
      • It updates the mask by setting the bit corresponding to i to 1 (simulating the choice).
      • It recursively calls dfs with the updated mask and currentSum + i.
      • If the recursive call returns false (meaning the next player loses), the current player wins, so we return true.
    • If none of the available numbers lead to a win for the current player, the current player loses, and we return false.

  4. Memoization: To avoid redundant calculations, we use a memoization table (f or a cache in Python) to store the results of previous dfs calls. The key is the bitmask, and the value is whether the current player (the one whose turn it is) wins in that state. This drastically improves performance.

Time and Space Complexity:

  • Time Complexity: O(N * 2N), where N is maxChoosableInteger. In the worst case, we might explore all possible subsets of the numbers. The memoization significantly reduces the actual computation time.
  • Space Complexity: O(2N) due to the memoization table (to store the results for all possible bitmasks).

Code Examples (Python, Java, C++, Go, TypeScript):

The code examples provided earlier demonstrate the implementation of this approach in various programming languages. The core logic remains consistent across all languages: a recursive depth-first search with memoization guided by a bitmask. The differences are primarily in syntax and data structure choices (e.g., HashMap in Java, unordered_map in C++, map in Go).