Here, We see Can I Win LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Can I Win LeetCode Solution
Table of Contents
Problem Statement
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
Can I Win LeetCode Solution C++
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int sum = maxChoosableInteger*(maxChoosableInteger+1)/2;
if (desiredTotal < 2) return true;
else if (sum < desiredTotal) return false;
else if (sum == desiredTotal) return maxChoosableInteger%2;
else return dfs(maxChoosableInteger, desiredTotal, 0);
}
bool dfs(int maxChoosableInteger, int desiredTotal, int k){
if (mem[k] != 0) return mem[k] > 0;
if (desiredTotal <= 0) return false;
for (int i = 0; i < maxChoosableInteger; ++i)
if (!(k&(1<<i)) && !dfs(maxChoosableInteger, desiredTotal-i-1, k|(1<<i))) {
mem[k] = 1;
return true;
}
mem[k] = -1;
return false;
}
int mem[1<<20] = {};
};
Code language: PHP (php)
Can I Win LeetCode Solution Java
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
int totalPossibleSum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
if (totalPossibleSum < desiredTotal) return false;
Map<Integer, Boolean> memo = new HashMap<>();
return dp(desiredTotal, 0, maxChoosableInteger, memo);
}
private boolean dp(int goal, int state, int maxChoosable, Map<Integer, Boolean> memo) {
if (memo.containsKey(state)) {
return memo.get(state);
}
boolean result = false;
for (int i = 1; i <= maxChoosable; i++) {
boolean isAvailable = (state >> i) % 2 == 0;
if (!isAvailable) {
continue;
}
if (goal - i <= 0) {
result = true;
break;
}
int currMask = 1 << i;
int newState = state | currMask;
boolean rivalResult = dp(goal - i, newState, maxChoosable, memo);
if (!rivalResult) {
result = true;
break;
}
}
memo.put(state, result);
return result;
}
}
Code language: JavaScript (javascript)
Can I Win Solution JavaScript
var canIWin = function (maxChoosableInteger, desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true;
if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) return false;
const memo = new Map;
const canWin = (state, total) => {
if (total >= desiredTotal) return false;
if (memo.has(state)) return memo.get(state);
for (let i = 1; i <= maxChoosableInteger; i++) {
const mask = 1 << i;
if ((state & mask) === 0) {
const next = state | mask;
if (!canWin(next, total + i)) {
memo.set(state, true);
return true;
}
}
}
memo.set(state, false);
return false;
}
return canWin(0, 0)
};
Code language: JavaScript (javascript)
Can I Win Solution Python
class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
has_used = lambda flag, x: flag & (1<<x)
is_odd = lambda x: x % 2 == 1
def can_player_win_on(target, bitflag):
if target <= 0:
return False
for call_number in range(1, maxChoosableInteger+1):
if has_used( bitflag, call_number ):
continue
if not can_player_win_on(target - call_number, bitflag | (1<<call_number) ):
return True
return False
S = maxChoosableInteger * (maxChoosableInteger+1) // 2
if S < desiredTotal:
return False
elif desiredTotal <= 0:
return True
elif S == desiredTotal and is_odd(maxChoosableInteger):
return True
return can_player_win_on(desiredTotal, bitflag=0 )