Can I Win: Bitmask Game Theory

Game Theory · Hard · Free problem

Two players take turns picking numbers from a shared pool $\{1, 2, \ldots, M\}$, where $M$ is the max choosable integer. Each number can only be picked once. A running total is kept -- whoever pushes the total to at least $T$ (the desired total) on their turn wins. Both players play optimally.

You go first. Can you guarantee a win?

Constraints:

  • \leq M \leq 20$
  • $0 \leq T \leq 300$

Examples:

  1. $M = 10$, $T = 11$: Output false. No matter what the first player picks, the second player can always counter and reach 11 first.
  2. $M = 10$, $T = 0$: Output true. The target is already met before anyone moves, so the first player wins immediately.
  3. $M = 4$, $T = 6$: Output true. First player picks 4, bringing the total to 4. Whatever the second player picks (1, 2, or 3), first player can finish off to reach 6.

Hints

  1. The order of picks does not matter -- only the SET of numbers already chosen determines the game state. Think about how to encode that set compactly.
  2. With $M \leq 20$, a bitmask fits the set of chosen numbers in a single integer. The running total is the sum of bits set, so the full state is just the mask -- memoize can_win(mask) recursively.
  3. Before running the DP, check two edge cases: if $T \leq 0$ return true immediately; if $\sum_{i=1}^{M} i < T$ no one can ever win, return false. Then implement the minimax: current player wins if any choice $i$ either hits the target or forces the opponent into a losing mask.

Worked Solution

How to Think About It: This is a two-player zero-sum combinatorial game with perfect information -- the kind of thing that shows up in algorithmic interviews as a test of whether you recognize the minimax pattern. Brute force means exploring every sequence of picks, which is $M!$ in the worst case -- far too slow for $M = 20$. The key observation: the order in which numbers were picked does not matter, only WHICH numbers have been picked and what the running total is. That collapses the state space dramatically. Since $M \leq 20$, we can represent the set of used numbers as a bitmask of up to 20 bits -- at most

^{20} \approx 10^6$ states, each answerable in $O(M)$ work. That gives a tractable $O(2^M \cdot M)$ DP.

Algorithm:

Define can_win(mask) as: can the player whose turn it is guarantee a win, given that the set of already-chosen numbers is encoded by mask? The running total is implicit -- it is the sum of all bits set in mask. At each state, the current player tries every unchosen number $i$. If choosing $i$ either immediately hits the target (running total + $i \geq T$) or leaves the opponent in a losing state (!can_win(mask | (1 << (i-1)))), then can_win(mask) = true. If no such $i$ exists, can_win(mask) = false.

Two edge cases to handle before the DP: - If $T = 0$, first player wins immediately (target already met). - If the sum of all numbers

+ 2 + \cdots + M = M(M+1)/2 < T$, neither player can ever reach $T$ -- return false.

Memoize results keyed on the bitmask (the total is determined by the mask, so no extra dimension is needed).

Code:

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

memo = {}

def can_win(mask, current_total): if mask in memo: return memo[mask] for i in range(1, maxChoosableInteger + 1): bit = 1 << (i - 1) if mask & bit: continue # already chosen if current_total + i >= desiredTotal: memo[mask] = True return True if not can_win(mask | bit, current_total + i): memo[mask] = True return True memo[mask] = False return False

return can_win(0, 0) ```

Complexity:

^M$ distinct masks, each requiring $O(M)$ work to iterate candidates.
  • Space: $O(2^M)$ for the memoization table.

    • For $M = 20$: roughly 0 \times 10^6$ operations -- fast.

    Answer: Use bitmask DP with memoization on the set of chosen numbers. The state is the bitmask; the current total is derived from it. Time $O(2^M \cdot M)$, space $O(2^M)$.

    Intuition

    The core lesson here is state compression via bitmask. In many combinatorial games, the naive state space is huge because it tracks history -- but once you recognize that only a SUMMARY of history matters (which items remain, not in what order they were taken), you can collapse exponentially many histories into a polynomial or low-exponential number of states. Bitmasks are the natural data structure when the summary is a subset of a small universe ($M \leq 20$ here).

    In quant interviews, this pattern appears beyond pure coding questions. Optimal liquidation problems, multi-period resource allocation, and sequential hedging decisions all share this structure: the relevant state is often a compact summary of what resources remain, not the full path that got you there. Recognizing when path-independence holds -- and exploiting it to compress state -- is a fundamental skill for anyone building combinatorial or dynamic programming models in trading or risk.

    Open the full interactive solver →