algoadvance

Leetcode 464. Can I Win

Problem Statement

You are given two integers maxChoosableInteger and desiredTotal. You can only choose an integer from 1 to maxChoosableInteger each time. Each integer can only be chosen once. The player who makes the total sum reach or exceed the desiredTotal first is the winner.

Assume that both players play optimally. Return true if the first player to move can force a win, otherwise return false.

Clarifying Questions

1. What are the constraints on maxChoosableInteger and desiredTotal?
   • 1 <= maxChoosableInteger <= 20
   • 0 <= desiredTotal <= 300
2. Can desiredTotal be zero?
   • Yes, if desiredTotal is zero, the first player automatically loses because they cannot make a move and hence cannot win.
3. Is it guaranteed that maxChoosableInteger will be enough to reach the desiredTotal?
   • This needs to be checked within the function. If the sum of the sequence 1 + 2 + ... + maxChoosableInteger is less than desiredTotal, it’s impossible for any player to win.

Strategy

1. Edge Case:
   • If desiredTotal is 0 the first player loses by definition since no moves lead to a win.
2. Sum Check:
   • If the sum of all numbers from 1 to maxChoosableInteger is less than desiredTotal, then it’s impossible for any player to reach the desiredTotal. Return false in this case.
3. Dynamic Programming with Memoization:
   • Use a combination of bit masking and memoization to keep track of visited states.
   • A recursive helper function will determine whether the current player can force a win given the current state of choices.
4. Recursive Logic:
   • From the current state, the player tries each available move (i.e., picking each unused number). Then, recursively solve for the new state (with the chosen number removed from available choices).
   • If any move leads to a situation where the opponent is destined to lose, the current state is a winning state.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2;

        // If the sum of all available numbers is less than the desiredTotal, there's no way to reach the target
        if (sum < desiredTotal) {
            return false;
        }

        // Use memoization to remember previously computed states
        Map<Integer, Boolean> memo = new HashMap<>();
        
        return canIWinHelper(maxChoosableInteger, desiredTotal, 0, memo);
    }

    private boolean canIWinHelper(int maxChoosableInteger, int total, int usedNumbers, Map<Integer, Boolean> memo) {
        if (total <= 0) {
            return false;
        }

        if (memo.containsKey(usedNumbers)) {
            return memo.get(usedNumbers);
        }

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

            // If the number i is already used, continue
            if ((usedNumbers & currentMask) != 0) {
                continue;
            }

            // If choosing i wins the game, or forces the opponent to lose on their turn
            if (total - i <= 0 || !canIWinHelper(maxChoosableInteger, total - i, usedNumbers | currentMask, memo)) {
                memo.put(usedNumbers, true);
                return true;
            }
        }

        memo.put(usedNumbers, false);
        return false;
    }
}

Time Complexity

• The time complexity is difficult to determine precisely because the problem is inherently exponential in nature with respect to maxChoosableInteger.
• However, memoization significantly trims down the number of recursive calls by storing and re-using results of previously computed states.
• In the worst case, the complexity is O(2^N * N) where N is maxChoosableInteger because there are 2^N possible combinations of states and for each state, we may check up to N possibilities.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?