464. Can I Win
Model: qwen3.5:9b
Topics: Dynamic Programming,Minimax
FAANG asked: 0
Acceptance rate: 29.7%
Problem Breakdown
We are analyzing a zero-sum game where two players take turns picking integers from the range [1, maxChoosableInteger] without replacement (no reuse allowed). The goal is to be the first player whose cumulative sum reaches or exceeds desiredTotal. We need to determine if Player 1 can force a win assuming optimal play from both sides.
Inputs:
maxChoosableInteger: Upper bound of available numbers (), .desiredTotal: The target sum threshold, .
Outputs:
- Boolean: True if Player 1 has a winning strategy.
Implicit Constraints & Edge Cases:
- Impossible Win Condition: If the sum of all available numbers () is less than
desiredTotal, no one can ever reach the target, so return False immediately. - Instant Win: If
desiredTotal, Player 1 wins instantly (base case). - State Representation: Since , we cannot use a simple set for memoization keys efficiently due to overhead; a bitmask is optimal ( lookup/insertion) because it fits within standard integer types.
Intuition
This problem models a game theory scenario, specifically Minimax with perfect information.
Brute Force Approach: A naive recursive solution would try every available number at each step and recurse until the target is reached or no moves remain. However, this leads to exponential time complexity because we re-evaluate identical states (same set of used numbers) multiple times across different move orders.
Key Insight:
- Game State Uniqueness: The state of the game depends entirely on which numbers have been picked so far and how much total remains to be reached. Since every number is unique, a bitmask can represent exactly which integers are available (or used).
- Memoization Key Optimization: Notice that if we know
maxChoosableIntegeranddesiredTotal, the current running sum is implicitly determined by the set of numbers already picked. Therefore, the specific “remaining total” doesn’t need to be part of our memo key; it’s derived from the initial target minus the sum of used bits in the mask. We only need to store results based onmask. - Winning Condition: For any state (defined by available numbers), if there exists any move that leads to a losing state for the opponent, then this current player wins. If all possible moves lead to states where the opponent can win, then this current player loses.
Approach
- Pre-checks:
- Calculate sum of . If
sum < desiredTotal, return False (impossible). - If
desiredTotal <= 0, return True (instant win).
- Calculate sum of . If
- Recursive Function with Memoization (
can_win):- Takes a bitmask representing used numbers.
- Iterate through all possible moves ( to ) that haven’t been picked yet.
- For each move, update the mask and recurse for the opponent’s turn.
- Logic: If
can_win(next_state)returns False (meaning the opponent loses from there), then we found a winning move, so return True immediately.
- Base Case: When no moves are available or remaining total is , handle appropriately. Note: The recursion naturally handles “remaining total” logic by checking if
desiredTotal - current_sum <= 0before recursing? Actually, simpler to pass the mask and check win condition at start of function call (if sum used >= desiredTotal). However, standard implementation usually passes remaining target or checks inside loop. To keep state minimal on Mask:- We can track
remaining = initial_desired - current_sum. - Wait, simpler logic for the code below: The mask represents available numbers? Or used numbers? Let’s use a mask where bit is set if number has been used. If
(mask & (num-1))is 0, it meansnumis available. - Wait, actually passing the remaining total in recursion arguments makes logic clearer for “win condition check”, but we established earlier that mask implies sum used. Let’s stick to Mask + Memoization on Mask only if possible?
- Actually, standard solution often passes
(mask)and checksdesiredTotalimplicitly or explicitly. To be safe and clear: We will pass the current remaining target in recursion arguments for clarity of logic inside function, but memoize based on mask because sum is deterministic from mask + initial total.
- We can track
- Memoization: Store results
{mask -> boolean}to avoid recomputing states.
Complexity Analysis
- Time Complexity: . There are possible masks (states). For each state, we iterate up to times to find a valid move. Given the constraint , this is roughly million operations in worst case, which fits within typical time limits for Python if optimized with memoization and pruning.
- Space Complexity: to store the memoization table (hash map).
Solution
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
# Edge Case 1: Impossible to reach target even if we use all numbers.
total_sum = maxChoosableInteger * (maxChoosableInteger + 1) // 2
if total_sum < desiredTotal:
return False
# Edge Case 2: Target already met or negative, Player 1 wins immediately.
if desiredTotal <= 0:
return True
memo = {}
def can_win(mask):
"""
mask bit i set means number (i+1) is used/unavailable.
We want to find a move that makes the opponent lose.
If we pick 'num', new_mask has num marked as used.
Recurse for opponent's turn. If they return False, we win.
"""
# Check memoization cache first
if mask in memo:
return memo[mask]
# Iterate through all available numbers (1 to maxChoosableInteger)
for num in range(1, maxChoosableInteger + 1):
# If bit corresponding to 'num' is not set, number is available
if not ((mask >> (num - 1)) & 1):
new_mask = mask | (1 << (num - 1))
# Recursive call: opponent's turn with updated state.
# We win if the recursive result for the opponent is False (they lose).
if not can_win(new_mask):
memo[mask] = True
return True
# If no move leads to a winning outcome, we lose from this state.
memo[mask] = False
return False
# Start with mask 0 (no numbers used yet)
return can_win(0)
Edge Cases Handled
desiredTotal <= 0: ReturnsTrueimmediately, as the condition is met before any moves.- Sum of all integers <
desiredTotal: ReturnsFalseat initialization since it’s impossible to reach the target regardless of strategy. - Single Number Available: The loop handles cases where only one number remains; if picking that number wins, logic holds. If not (e.g., remaining sum insufficient), recursion terminates and returns False correctly.
- Max Choosable Integer = 20: Bitmask fits within standard integer types in Python (arbitrary precision) without overflow issues.