Nim Game

XXX. Nim Game

Mathematics

Game Theory

Problem Statement:

You are playing the Nim Game with another player. Initially, there is a heap of n stones, and you take turns removing 1 to 3 stones. The player who removes the last stone wins. Determine if you can win the game given n stones and that you always go first.

Algorithm:

The problem is based on a mathematical observation:

1. If the number of stones n is divisible by 4, you will lose if your opponent plays optimally. This is because no matter how many stones you remove (1, 2, or 3), your opponent can always adjust their move to keep the total stones left divisible by 4.
2. If n % 4 != 0, you can always adjust your moves to force your opponent into a losing position (where the stones left are divisible by 4).

Complexity:

Time Complexity: O(1), since the solution only involves a modulo operation.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

class Solution {
    public boolean canWinNim(int n) {
        // You win if n is not divisible by 4
        return (n % 4) != 0;
    }
}