In this guide, you will get 464. Can I Win LeetCode Solution with the best time and space complexity. The solution to Can I Win problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0)
return true;
const int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
if (sum < desiredTotal)
return false;
unordered_map<int, bool> mem;
return canIWin(desiredTotal, 0, maxChoosableInteger, mem);
}
private:
// Returns true if the first player can we, where `used` represents the used
// numbers.
bool canIWin(int total, int used, const int& maxChoosableInteger,
unordered_map<int, bool>& mem) {
if (total <= 0)
return false;
if (const auto it = mem.find(used); it != mem.cend())
return it->second;
for (int i = 1; i <= maxChoosableInteger; ++i) {
if (used >> i & 1) // Integer i is used.
continue;
if (!canIWin(total - i, used | 1 << i, maxChoosableInteger, mem))
return true;
}
return mem[used] = false;
}
}; /* code provided by PROGIEZ */
464. Can I Win LeetCode Solution in Java
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0)
return true;
final int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
if (sum < desiredTotal)
return false;
Map<Integer, Boolean> mem = new HashMap<>();
return canIWin(desiredTotal, 0, maxChoosableInteger, mem);
}
// Returns true if the first player can we, where `used` represents the used
// numbers.
private boolean canIWin(int total, int used, int maxChoosableInteger, Map<Integer, Boolean> mem) {
if (total <= 0)
return false;
if (mem.containsKey(used))
return mem.get(used);
for (int i = 1; i <= maxChoosableInteger; ++i) {
if ((used >> i & 1) == 1) // Integer i is used.
continue;
if (!canIWin(total - i, used | 1 << i, maxChoosableInteger, mem))
return true;
}
mem.put(used, false);
return false;
}
} // code provided by PROGIEZ
464. Can I Win LeetCode Solution in Python
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
if desiredTotal <= 0:
return True
totalSum = maxChoosableInteger * (maxChoosableInteger + 1) // 2
if totalSum < desiredTotal:
return False
@functools.lru_cache(None)
def dp(total: int, used: int) -> bool:
"""
Returns true if the first player can we, where `used` represents the use
numbers.
"""
if total <= 0:
return False
return any((used >> i & 1) == 0
and not dp(total - i, used | 1 << i)
for i in range(1, maxChoosableInteger + 1))
return dp(desiredTotal, 0) # code by PROGIEZ
