Leetcode 464. Can I Win

Explanation

This problem is based on game theory and states that, in the 100 game, two players take turns adding an integer from 1 to any other number called maxChoosableInteger to a running sum. The one who causes this sum to reach or exceed a number called desiredTotal wins. The condition is that players cannot re-use integers.

Essentially, we're asked whether the first player can force a win with optimal gameplay and given the limit for the maximum number that can be chosen (maxChoosableInteger) and the target total sum (desiredTotal).

We can solve this with a Dynamic Programming (DP) approach and Bit Manipulation for optimization. Let's consider an example with maxChoosableInteger = 10, desiredTotal = 11:

1. If the sum of 1 to maxChoosableInteger is less than desiredTotal, then it's impossible for any player to reach the desiredTotal. In our example, sum of 1 to 10 is 55, which is less than the desiredTotal (11), and so no one can win.

2. We then define a memo dictionary to store the result of whether a player can win in a certain state. The state represents which integers have been used.

3. We loop through all the integers and if an integer has not been used and causes the total to reach or exceed the desiredTotal, or if the next state is false (the next player cannot win), then the player can force a win.

4. For each state, if no integers can force the player to win, we set memo[state] to false and return false.

Let's see how this works in different languages.

C++ Solution

1
2c++
3class Solution {
4 public:
5  bool canIWin(int maxChoosableInteger, int desiredTotal) {
6    
7    if (desiredTotal <= 0) {
8      return true;
9    }
10  
11    int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
12    if (sum < desiredTotal) {
13      return false;
14    }
15
16    memo = unordered_map<int, bool>();
17    return dp(desiredTotal, 0, maxChoosableInteger);
18  }
19
20 private:
21  unordered_map<int, bool> memo;
22
23  bool dp(int total, int state, int n) {
24    
25    if (total <= 0) {
26      return false;
27    }
28
29    auto it = memo.find(state);
30    if (it != memo.end()) {
31      return it->second;
32    }
33    
34    for (int i = 1; i <= n; ++i) {
35      // Bit operation to check if integer i is used
36      if (state & (1 << i)) {
37        continue;
38      }
39      // If integer i is not used and the next state is unwinnable for next player
40      if (!dp(total - i, state | (1 << i), n)) {
41        return memo[state] = true;
42      }
43    }
44
45    memo[state] = false;
46    return false;
47  }
48};

One main point in the C++ solution is the use of an unordered_map to quickly access the state of the game.

Java Solution

1
2java
3class Solution {
4    private Boolean[] memo;
5    
6    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
7        if (maxChoosableInteger <= 0 || desiredTotal <= 0) {
8            return true;
9        }
10        
11        if ((1+maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
12            return false;
13        }
14
15        memo = new Boolean[1 << (maxChoosableInteger+1)];
16        return helper(maxChoosableInteger, desiredTotal, 0);
17    }
18    
19    private boolean helper(int maxChoosableInteger, int desiredTotal, int state) {
20        if (desiredTotal <= 0) return false;
21        if (memo[state] != null) return memo[state];
22        
23        for (int i = 1; i <= maxChoosableInteger; i++) {
24            if ((state & (1 << i)) == 0) {
25                if (!helper(maxChoosableInteger, desiredTotal - i, state | (1 << i))) {
26                    memo[state] = true;
27                    return true;
28                }
29            }
30        }
31        
32        memo[state] = false;
33        return false;
34    }
35}

In this Java solution, an array of Booleans memo is created using bitwise operations.

Python Solution

1
2python
3class Solution:
4    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
5        if desiredTotal <= 0:
6            return True
7
8        if sum(range(1, maxChoosableInteger + 1)) < desiredTotal:
9            return False
10
11        self.memo = {}
12        return self.dp(range(1, maxChoosableInteger + 1), desiredTotal)
13
14    def dp(self, pool, total):
15        # use tuple(sorted(pool)) as the state key
16        key = tuple(sorted(pool))
17        if key in self.memo:
18            return self.memo[key]
19
20        for num in pool:
21            # total-num meaning the next player needs to reach total-num
22            next_pool = [i for i in pool if i != num]
23            # if num >= total, meaning the current player can win
24            # if self.dp(next_pool, total-num) is False, meaning the next player can not win, then the current player can win
25            if num >= total or not self.dp(next_pool, total - num):
26                self.memo[key] = True
27                return True
28
29        self.memo[key] = False
30        return False

In this Python solution, next_pool is a list of numbers that have not been chosen yet, and self.memo is a dictionary storing the result whether a player can win in the current state.## JavaScript Solution

1
2javascript
3class Solution {
4    canIWin(maxChoosableInteger, desiredTotal) {
5        if (desiredTotal <= 0) return true;
6
7        const sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2;
8        if (sum < desiredTotal) return false;
9
10        this.memo = new Map();
11        return this.dp(desiredTotal, 0, maxChoosableInteger);
12  }
13
14  dp(total, state, n) {
15      if (total <= 0) return false;
16
17      if (this.memo.has(state)) return this.memo.get(state);
18      
19      for (let i = 1; i <= n; ++i) {
20          if (state & (1 << i)) continue;
21
22          if (!this.dp(total - i, state | (1 << i), n)) {
23              this.memo.set(state, true);
24              return true;
25          }
26      }
27
28      this.memo.set(state, false);
29      return false;
30  }
31};
32
33const solution = new Solution;
34console.log(solution.canIWin(10, 11));  // Expected output: true

In JavaScript, we use a map object this.memo to store the winnable states for a player at a given total. We use bitwise operators exactly as in previous solutions to check whether a number was chosen or not and to set it to selected. For example, the bitwise AND & operator is used to check if an integer is already used. To set an integer as used, the bitwise OR | operator is used.