Solution Explanation for Nim Game

The Nim game is a mathematical game of strategy. The solution leverages a key observation about winning strategies in this specific version of the game.

Core Idea: The game's outcome hinges entirely on whether the number of stones (n) is a multiple of 4.

• If n is a multiple of 4: The first player (you) is guaranteed to lose. No matter how many stones (1, 2, or 3) you remove, your opponent can always leave a multiple of 4 stones for you on your next turn. This continues until you're left with 0 stones, resulting in your loss.

• If n is not a multiple of 4: The first player (you) is guaranteed to win. You can strategically remove stones to leave a multiple of 4 for your opponent, forcing them into the losing position described above.

Algorithm:

The solution is remarkably simple: check if n is divisible by 4 using the modulo operator (%). If the remainder is not 0, you win; otherwise, you lose.

Time and Space Complexity:

• Time Complexity: O(1) - The modulo operation is a constant-time operation, regardless of the size of n.

• Space Complexity: O(1) - The solution uses a constant amount of extra space. No matter how large n is, we only store a few variables.

Code Implementations:

The code implementations across different languages are almost identical because the core logic is so concise. They all perform the same modulo operation and return the result directly.

Example Code (Python):

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

Example Code (Java):

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

Example Code (C++):

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

Example Code (Go):

func canWinNim(n int) bool {
	return n%4 != 0
}

Example Code (TypeScript):

function canWinNim(n: number): boolean {
    return n % 4 != 0;
}

Example Code (Rust):

impl Solution {
    pub fn can_win_nim(n: i32) -> bool {
        n % 4 != 0
    }
}

All of these code snippets efficiently implement the core idea described above. They all have the same time and space complexity.