Can I Win — Solution in Python, Java & C++
Can I Win solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Can I Win is a medium coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and LinkedIn interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Bit Manipulation, Bitmask, Memoization, Game Theory
- Asked at: Amazon, Google, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two players share a running total that starts at 0. They take turns, and on each turn a player picks one of the integers 1, 2, …, maxChoosableInteger and adds it to the total. Each integer can be picked only once in the whole game, by either player.
The player whose pick makes the running total reach or exceed desiredTotal wins.
The first player moves first. Assuming both players always play optimally, return true if the first player can force a win, and false otherwise. (If the numbers run out before the total is reached, nobody reaches it, and the first player has not won.)
Example 1
Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation: Whatever x the first player picks, the second player picks 11 - x (always available and different from x) and reaches 11.
Example 2
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
Explanation: The target is already met before anyone moves.
Example 3
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
Explanation: Any pick reaches 1.
Constraints
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
Hints for Can I Win
Hint 1
Two quick answers first: a target
<= 0is already won, and if1 + 2 + … + maxChoosableInteger < desiredTotalnobody can ever reach it.Hint 2
The remaining total is determined by which numbers have been used, so the whole game state is the set of used numbers — at most
2^20states. Encode it as a bitmask.Hint 3
The player to move wins from a state if some unused
ieither reaches the target immediately (i >= remaining) or leads to a state from which the opponent loses. Memoise win/lose per mask.
How to solve Can I Win
This is a finite two-player game without chance, so every position is a forced win or a forced loss for the player to move. The position is fully described by the set of numbers already used (the remaining target follows from it), so memoising over a bitmask of used numbers makes the game tree a DAG of at most 2^m nodes.
Approach
- If
desiredTotal <= 0returntrue; ifm(m+1)/2 < desiredTotalreturnfalse(m = maxChoosableInteger). - Define
win(used, remaining): for eachiin1..mnot inused, ifi >= remainingor!win(used | bit(i), remaining - i), returntrue. Otherwise returnfalse. - Cache the result by
used(an array of size2^(m+1)with unknown / win / lose). - Return
win(0, desiredTotal).
Why it works
A move that reaches the target wins on the spot; any other move hands the opponent the position used | bit(i) with them to move. The mover can force a win exactly when some move leaves the opponent in a losing position — the standard win/lose recursion. Since remaining = desiredTotal - sum(used), two calls with the same mask always have the same remaining total, so caching by mask alone is sound.
Complexity
- Time —
O(2^m * m) - Space —
O(2^m)
Pitfalls
- Without the
sum < desiredTotalcheck, a game where nobody can win would be reported as a loss for the first player only by accident of the recursion — the check makes it explicit and fast. desiredTotal = 0is a win for the first player even though no move is made.- Memoising on
(used, remaining)as a string key is correct but slow; the mask alone is enough.
Reference solution
Python
def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool:
m = maxChoosableInteger
if desiredTotal <= 0:
return True
if m * (m + 1) // 2 < desiredTotal:
return False
memo = {}
def win(used, remaining):
if used in memo:
return memo[used]
res = False
for i in range(1, m + 1):
bit = 1 << i
if used & bit:
continue
if i >= remaining or not win(used | bit, remaining - i):
res = True
break
memo[used] = res
return res
return win(0, desiredTotal)Java
static byte[] canWinMemo;
static int canWinMax;
static boolean canWin(int used, int remaining) {
if (canWinMemo[used] != 0) return canWinMemo[used] == 1;
boolean res = false;
for (int i = 1; i <= canWinMax; i++) {
int bit = 1 << i;
if ((used & bit) != 0) continue;
if (i >= remaining || !canWin(used | bit, remaining - i)) { res = true; break; }
}
canWinMemo[used] = (byte) (res ? 1 : 2);
return res;
}
public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
int m = maxChoosableInteger;
if (desiredTotal <= 0) return true;
if (m * (m + 1) / 2 < desiredTotal) return false;
canWinMax = m;
canWinMemo = new byte[1 << (m + 1)];
return canWin(0, desiredTotal);
}C++
bool canWinFrom(int used, int remaining, int m, vector<signed char>& memo) {
if (memo[used] != 0) return memo[used] == 1;
bool res = false;
for (int i = 1; i <= m; i++) {
int bit = 1 << i;
if (used & bit) continue;
if (i >= remaining || !canWinFrom(used | bit, remaining - i, m, memo)) { res = true; break; }
}
memo[used] = res ? 1 : 2;
return res;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int m = maxChoosableInteger;
if (desiredTotal <= 0) return true;
if (m * (m + 1) / 2 < desiredTotal) return false;
vector<signed char> memo(1 << (m + 1), 0);
return canWinFrom(0, desiredTotal, m, memo);
}JavaScript
var canIWin = function(maxChoosableInteger, desiredTotal) {
var m = maxChoosableInteger;
if (desiredTotal <= 0) return true;
if (m * (m + 1) / 2 < desiredTotal) return false;
var memo = new Int8Array(1 << (m + 1)); // 0 unknown, 1 win, 2 lose
var win = function(used, remaining) {
if (memo[used] !== 0) return memo[used] === 1;
var res = false;
for (var i = 1; i <= m; i++) {
var bit = 1 << i;
if (used & bit) continue;
if (i >= remaining || !win(used | bit, remaining - i)) { res = true; break; }
}
memo[used] = res ? 1 : 2;
return res;
};
return win(0, desiredTotal);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Bit Manipulation