algoadvance

Leetcode 464. Can I Win

Problem Statement

The “Can I Win” problem from LeetCode (#464) is defined as follows:

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 the players cannot re-use integers?

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:

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player chooses, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player chooses 10, the second player can choose 1, which causes the first player to lose.
If the first player chooses 9, the second player can choose 2, which causes the first player to lose.
...

Clarifying Questions

  1. Constraints on maxChoosableInteger and desiredTotal:
    • What is the range of values for maxChoosableInteger and desiredTotal?

    From the problem description:

    • 1 <= maxChoosableInteger <= 20
    • 0 <= desiredTotal <= 300
  2. Initial choices and turns:
    • Is the game always starting with the first player making the first move?

    Yes, the first move is always made by the first player.

Code

Here’s a C++ implementation using memoization and bitmasking to optimize the solution:

#include <iostream>
#include <unordered_map>

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        if ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2 < desiredTotal) return false;
        unordered_map<int, bool> memo;
        return canIWin(maxChoosableInteger, desiredTotal, 0, memo);
    }

private:
    bool canIWin(int maxChoosableInteger, int desiredTotal, int usedNumbers, unordered_map<int, bool>& memo) {
        if (memo.find(usedNumbers) != memo.end()) return memo[usedNumbers];
        
        for (int i = 0; i < maxChoosableInteger; ++i) {
            int current = (1 << i);
            if ((current & usedNumbers) == 0) {
                if (desiredTotal - (i + 1) <= 0 || !canIWin(maxChoosableInteger, desiredTotal - (i + 1), usedNumbers | current, memo)) {
                    return memo[usedNumbers] = true;
                }
            }
        }
        return memo[usedNumbers] = false;
    }
};

Strategy

  1. Immediate Win Check:
    • If desiredTotal is zero or negative initially, the first player trivially wins by doing nothing (return true).
  2. Infeasibility Check:
    • Calculate the maximum sum possible using all numbers from 1 to maxChoosableInteger. If this sum is less than desiredTotal, it is impossible for any player to win (return false).
  3. Memoization:
    • Use a dictionary (unordered_map) to memoize the results of subproblems. The key is the usedNumbers bitmask indicating which numbers have been used.
  4. Bitmasking:
    • Use a bitmask to track used numbers. The i-th bit in usedNumbers is set if the (i+1) number has been used.
  5. Core Logic:
    • Loop through all possible choices for the current player.
    • If choosing a number leads to a win (by forcing the next player into a losing state), memoize and return true.
    • If no such choice exists, memoize and return false.

Time Complexity

The complexity of this approach can be expressed as O(2^n * n), where n is maxChoosableInteger:

Therefore, the time complexity is exponential in the worst case. However, it’s feasible within the problem’s constraints due to the pruning of states and memoization.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI