[LeetCode] Can I Win

Problem: 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:

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.

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

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

Constraints:

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

Approach: We can use simple recursion (DFS) to solve this question. We can do something like following:

• FOR i = 1 TO maxChoosableInteger
• IF i is not used
• // 1st player can win if desired total can be achieved or second player can't win
• IF desiredTotal <= i OR NOT CanWin(desiredTotal - i)
• RETURN True
• RETURN False

The only problem in the above solution is the time complexity which is !n where n is maxChoosableInteger.  We can improve it using memorization  / DP. If you see we are solving the problem for same state again and again. We can basically memorize that at a certain state (used integers) the 1st player won or not and we can use it to make this program efficient.

Implementation in C#:

    public bool CanIWin(int maxChoosableInteger, int desiredTotal) 

    {

        if (maxChoosableInteger >= desiredTotal)

        {

            return true;

        }

        if (desiredTotal > ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2))

        {

            return false;

        }

        // Can use a integer to keep track of what ints are already used as maxChoosableInteger 

       // is not more than 20

        int currState = 0;

        //memorization: currState(Used Integers) => Player 1 win / loss (true / false)

        Dictionary<int, bool> table = new Dictionary<int, bool>();

        return this.CanWin(maxChoosableInteger, desiredTotal, currState, table);

    }

    

    public bool CanWin(

        int maxChoosableInteger, 

        int desiredTotal, 

        int currState, 

        Dictionary<int, bool> table)

    {

        if (table.ContainsKey(currState))

        {

            return table[currState];

        }

        for (int i = 1; i <= maxChoosableInteger; ++i)

        {

            // Integer is already used

            if ((currState & (1 << (i - 1))) != 0)

            {

                continue;

            }

            // total achieved or second player lost

            if (desiredTotal <= i || 

                !CanWin(maxChoosableInteger, desiredTotal - i, (currState | (1 << (i - 1))), table))

            {

                table[currState] = true;

                return true;

            }

        }

        table[currState] = false;

        return false;

    }

Complexity: O(n * 2 ^ n)