Scale Engineer

Can I Win

Med
#0451Time: O(N!), where N is `maxChoosableInteger`. The function explores all permutations of numbers, leading to a factorial number of paths in the game tree.Space: O(N), where N is `maxChoosableInteger`. This space is used for the recursion stack depth and to store the set of used numbers.1 company
Patterns
MathDynamic ProgrammingBit ManipulationMemoizationGame TheoryBitmask
Companies
LinkedIn

Prompt

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.

 

Example 1:

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Example 2:

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Example 3:

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

 

Constraints:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the game by exploring every possible sequence of moves using a recursive function. It directly translates the game's rules into a recursive structure without any optimization for repeated computations. It represents the game tree and explores every path to determine if a winning strategy exists for the first player.

Algorithm

  • Create a recursive function canWin(usedNumbers, currentTotal).
  • Loop from i = 1 to maxChoosableInteger.
  • If i is not in usedNumbers:
    • If currentTotal + i >= desiredTotal, return true as this is a winning move.
    • Recursively call canWin for the opponent: opponentLoses = !canWin(usedNumbers + {i}, currentTotal + i).
    • If opponentLoses is true, it means we found a move that guarantees a win. Return true.
  • If the loop finishes without finding a winning move, it means all moves lead to the opponent winning. Return false.

Walkthrough

This approach models the game by exploring every possible sequence of moves using a recursive function. It directly translates the game's rules into a recursive structure without any optimization for repeated computations.

  • We define a recursive function, say canWinRecursive(usedNumbers, currentTotal), which returns true if the current player can force a win given the set of usedNumbers and the currentTotal.
  • In each call, the function iterates through all numbers from 1 to maxChoosableInteger.
  • For each available number, it simulates picking that number.
  • If picking a number i makes the currentTotal + i reach or exceed desiredTotal, the current player wins.
  • Otherwise, it makes a recursive call for the opponent's turn with the updated set of used numbers and the new total. The current player wins if the opponent loses in the subsequent state (i.e., the recursive call returns false).
  • If after trying all available numbers, no winning move is found, the current player loses.
  • This method explores the entire game tree, which includes many redundant calculations for the same game states reached through different sequences of moves.
// Conceptual code for brute-force recursionprivate boolean canWinRecursive(java.util.Set<Integer> used, int currentTotal, int maxChoosableInteger, int desiredTotal) {    // Iterate through all possible numbers    for (int i = 1; i <= maxChoosableInteger; i++) {        // If the number is not used yet        if (!used.contains(i)) {            // Check if this move wins            if (currentTotal + i >= desiredTotal) {                return true;            }                        // Make the move and recurse for the other player            used.add(i);            // If the other player CANNOT win, then this is a winning move for us            if (!canWinRecursive(used, currentTotal + i, maxChoosableInteger, desiredTotal)) {                used.remove(i); // Backtrack                return true;            }            used.remove(i); // Backtrack        }    }    // If no winning move is found    return false;}

Complexity

Time

O(N!), where N is `maxChoosableInteger`. The function explores all permutations of numbers, leading to a factorial number of paths in the game tree.

Space

O(N), where N is `maxChoosableInteger`. This space is used for the recursion stack depth and to store the set of used numbers.

Trade-offs

Pros

  • Simple to understand and implement as it directly models the game logic.

Cons

  • Extremely inefficient due to re-computation of the same subproblems.

  • The time complexity is factorial, making it infeasible for the given constraints.

  • Will result in a 'Time Limit Exceeded' error on most coding platforms.

Solutions

class Solution {private  Map<Integer, Boolean> memo = new HashMap<>();public  boolean canIWin(int maxChoosableInteger, int desiredTotal) {    int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;    if (s < desiredTotal) {      return false;    }    return dfs(0, 0, maxChoosableInteger, desiredTotal);  }private  boolean dfs(int state, int t, int maxChoosableInteger, int desiredTotal) {    if (memo.containsKey(state)) {      return memo.get(state);    }    boolean res = false;    for (int i = 1; i <= maxChoosableInteger; ++i) {      if (((state >> i) & 1) == 0) {        if (t + i >= desiredTotal ||            !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal)) {          res = true;          break;        }      }    }    memo.put(state, res);    return res;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem