We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Can I Win

Difficulty: Medium

Problem Description

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. If the game is changed so that players cannot re-use integers from a common pool of numbers from 1 to maxChoosableInteger until they reach a total >= desiredTotal, return true if the first player to move can force a win, otherwise return false. Assume both players play optimally.

Key Insights

  • The first player can force a win if they can make a move that guarantees the second player cannot win in their subsequent turn.
  • The game can be modeled using dynamic programming and memoization to keep track of previously computed states.
  • A bitmask can be used to represent the available integers that players can choose from, making it efficient to check which integers have been used.
  • The base cases are when the desiredTotal is 0 (first player wins) or when the first player's choice immediately wins the game.

Space and Time Complexity

Time Complexity: O(2^n) where n is the number of integers available (up to 20), due to the possible subsets of integers being considered. Space Complexity: O(2^n) for the memoization table storing results for each state.

Solution

The solution uses a recursive function with memoization to determine if the first player can win. The states are represented by a bitmask indicating which integers have been chosen, and the recursive checks all possible moves for the first player. If any move leads to a state where the second player cannot win, the first player is guaranteed a win.

Code Solutions

def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool:
    if desiredTotal <= 0:
        return True
    if (maxChoosableInteger * (maxChoosableInteger + 1)) // 2 < desiredTotal:
        return False

    memo = {}

    def canWin(remaining, total):
        if remaining in memo:
            return memo[remaining]

        for i in range(1, maxChoosableInteger + 1):
            if remaining & (1 << (i - 1)) == 0:  # if i has not been chosen
                if total + i >= desiredTotal or not canWin(remaining | (1 << (i - 1)), total + i):
                    memo[remaining] = True
                    return True

        memo[remaining] = False
        return False

    return canWin(0, 0)
← Back to All Questions