Algorithm
Problem Name: 464. Can I Win
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 1:
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.
Example 2:
Input: maxChoosableInteger = 10, desiredTotal = 0 Output: true
Example 3:
Input: maxChoosableInteger = 10, desiredTotal = 1 Output: true
Constraints:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int canWin(int *dp, int v, int m, int total) {
int i, hewins;
if (dp[v] != -1) return dp[v]; // already resolved
for (i = m; i >= 1; i --) {
if (v & (1 << (i - 1))) continue;
v |= (1 << (i - 1));
if (i >= total) {
dp[v] = 1; // resolve to win
return 1;
}
hewins = canWin(dp, v, m, total - i);
if (!hewins) return 1;
v &= ~(1 << (i - 1)); // not able to resolve, try with different number
}
dp[v] = 0; // resolve to loose
return 0;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int w, dp[1 << 20];
// none can win
if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
//dp = calloc((1 << (maxChoosableInteger)), sizeof(int));
//assert(dp);
memset(dp, -1, (1 << (maxChoosableInteger)) * sizeof(int));
w = canWin(dp, 0, maxChoosableInteger, desiredTotal);
//free(dp);
return w;
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const canIWin = function(maxChoosableInteger, desiredTotal) {
if (desiredTotal <= 0) return true
if ((maxChoosableInteger * (1 + maxChoosableInteger)) / 2 < desiredTotal)
return false
const dp = new Array(1 << maxChoosableInteger).fill(0)
return dfs(dp, 0, maxChoosableInteger, desiredTotal)
function dfs(dp, chs, max, target) {
if (target < = 0) return false
if (dp[chs] != 0) return dp[chs] === 1
let win = false
for (let i = 0; i < max; i++) {
if ((chs & (1 << i)) === 0) {
//not used
win = win || !dfs(dp, chs ^ (1 << i), max, target - i - 1)
}
}
dp[chs] = win ? 1 : -1
return win
}
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canIWin(self, maxChoosableInteger, desiredTotal):
memo = {}
def dfs(arr, total):
s = str(arr)
if s in memo:
return memo[s]
elif arr[-1] >= total:
return True
for i in range(len(arr)):
if not dfs(arr[:i] + arr[i + 1:], total - arr[i]):
memo[s] = True
return True
memo[s] = False
return False
if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
return False
return dfs(list(range(1, maxChoosableInteger + 1)), desiredTotal)
Input
Output