Dare2Solve
The problem is based on the classic "Nim Game." In this game, two players take turns removing 1 to 3 stones from a pile. The player who removes the last stone wins. Given an initial number of stones n
, determine if you can win the game assuming both players play optimally and you start first.
The key observation in the Nim Game is that if the number of stones n
is a multiple of 4, you will always lose if your opponent plays optimally. This is because, regardless of how many stones you remove (1, 2, or 3), your opponent can always return the count to a multiple of 4. If n
is not a multiple of 4, you can force the game into a losing position for your opponent by reducing the number of stones to the nearest multiple of 4.
n
is divisible by 4: If n
is a multiple of 4, return false
because you will lose if both players play optimally.true
: If n
is not a multiple of 4, return true
because you can always force your opponent into a losing position.O(1)
. The solution only requires a simple modulus operation, which is constant time.
O(1)
. No additional space is required beyond a few variables.
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
var canWinNim = function(n) {
if( n % 4 == 0) return false;
else return true;
};