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
:
-
If the sum of 1 to
maxChoosableInteger
is less thandesiredTotal
, then it's impossible for any player to reach thedesiredTotal
. In our example, sum of 1 to 10 is 55, which is less than thedesiredTotal
(11), and so no one can win. -
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. -
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. -
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.