Can i win

Math Dynamic Programming Bit Manipulation Memoization Game Theory Bitmask

31.0% acceptance

Jan 13, 2026

2826

431

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
impl Solution {
  pub fn can_i_win(max_choosable_integer: i32, desired_total: i32) -> bool {
    if desired_total <= 0 {
      return true;
    }

    let sum = (max_choosable_integer * (max_choosable_integer + 1)) / 2;
    if sum < desired_total {
      return false;
    }

    let mut memo = HashMap::new();
    Self::can_win(0, desired_total, max_choosable_integer, &mut memo)
  }

  fn can_win(state: i32, total: i32, max: i32, memo: &mut HashMap<i32, bool>) -> bool {
    if let Some(&result) = memo.get(&state) {
      return result;
    }

    for i in 1..=max {
      let mask = 1 << i;
      if state & mask == 0 {
        if total <= i || !Self::can_win(state | mask, total - i, max, memo) {
          memo.insert(state, true);
          return true;
        }
      }
    }

    memo.insert(state, false);
    false
  }
}