292. Nim Game

Description

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.

Intuition

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.

Approach

1. Check if n is divisible by 4: If n is a multiple of 4, return false because you will lose if both players play optimally.
2. Otherwise, return true: If n is not a multiple of 4, return true because you can always force your opponent into a losing position.

Complexity

Time Complexity:

O(1). The solution only requires a simple modulus operation, which is constant time.

Space Complexity:

O(1). No additional space is required beyond a few variables.

Code

C++

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

Python

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

Java

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

JavaScript

var canWinNim = function(n) {
    if( n % 4 == 0) return false;
    else return true;
};