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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Can I Win

Number: 464

Difficulty: Medium

Paid? No

Companies: LinkedIn, Amazon

Problem Description

Two players take turns selecting numbers from 1 to maxChoosableInteger without replacement. The selected numbers are added to a running total. The player whose move causes the total to reach or exceed desiredTotal wins. Determine if the first player can force a win, assuming both players play optimally.

Key Insights

  • Use recursion (DFS/backtracking) with memoization to evaluate game states.
  • Represent each game state with a bitmask tracking which numbers have been chosen.
  • Base case: if a chosen number is greater than or equal to the remaining total needed, it results in an immediate win for the current player.
  • Check if the sum of all numbers is less than desiredTotal; if so, the game cannot be won.
  • At each state, try every available number and let the opponent play optimally; if any move forces the opponent into a losing position, the current player wins.
  • The problem uses game theory logic: ensuring that if all subsequent moves lead to opponent’s wins, then current move is losing.

Space and Time Complexity

Time Complexity: O(2^maxChoosableInteger * maxChoosableInteger)
Space Complexity: O(2^maxChoosableInteger)

Solution

We use a recursive DFS approach with memoization to track the winning possibilities from each state. A bitmask (or integer state) is used to represent which numbers have been picked so far. The recursion simulates each move by subtracting the chosen number from the desired total. If a move results in a win (i.e., chosen number >= remaining total) or forces the opponent into a position where they cannot win, then we mark the state as winning for the current player. We store already computed states in a memo dictionary to avoid redundant computation.

Code Solutions

# Function to determine if the first player can force a win
def canIWin(maxChoosableInteger, desiredTotal):
    # If the sum of all available numbers is less than desiredTotal, no one can win
    if (maxChoosableInteger * (maxChoosableInteger + 1)) // 2 < desiredTotal:
        return False
    # When desiredTotal is 0, first player trivially wins
    if desiredTotal <= 0:
        return True

    memo = {}
    
    def canWin(usedNumbers, currentTotal):
        # If this state has been computed before, return the result immediately
        if usedNumbers in memo:
            return memo[usedNumbers]
        
        # Try every number from 1 to maxChoosableInteger
        for i in range(1, maxChoosableInteger + 1):
            # Bitmask to check if number i is already used
            curMask = 1 << i
            if usedNumbers & curMask == 0:  # number i is available
                # If choosing i wins the game immediately or forces opponent into a losing state
                if i >= currentTotal or not canWin(usedNumbers | curMask, currentTotal - i):
                    memo[usedNumbers] = True
                    return True
        # If for all moves, opponent can counter and win, current state is losing.
        memo[usedNumbers] = False
        return False

    return canWin(0, desiredTotal)

# Example test
print(canIWin(10, 11))  # Expected output: False
← Back to All Questions