Code Implementation

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

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

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

var canWinNim = function(n) {
    return n % 4 !== 0;
};
      

Problem Description

The Nim Game is a classic two-player game where there is a heap of n stones on a table. Players take turns removing 1, 2, or 3 stones from the heap. The player who removes the last stone wins the game.

You are given the number of stones n. You always go first. Each player takes turns optimally. The task is to determine whether you can win the game, assuming both players play optimally.

Constraints:

• 1 ≤ n ≤ 2³¹ - 1
• You must decide if you can guarantee a win starting first, not just if it is possible.
• Each move must remove 1, 2, or 3 stones.

Thought Process

The first instinct might be to simulate all possible moves, trying every possible number of stones to remove at each turn. However, this quickly becomes impractical for large values of n. Instead, we look for a pattern or mathematical insight.

By considering small values of n, we notice that:

• If there are 1, 2, or 3 stones, you can always win by taking all the stones.
• If there are 4 stones, no matter what you do (take 1, 2, or 3), your opponent can always take the remaining stones and win.
• If there are 5, 6, or 7 stones, you can always take enough stones to leave 4 for your opponent, forcing them into the losing position.
• If there are 8 stones, no matter what you do, your opponent can always force you back into a losing position.

Solution Approach

Let's break down the solution step-by-step:

1. Identify Losing Positions: The only way you can lose is if, after your turn, the number of stones left is a multiple of 4. This is because, no matter how many you take (1, 2, or 3), the other player can always take enough to bring it back to another multiple of 4, repeating this pattern until you are forced to take the last stone and lose.
2. Winning Strategy: If the number of stones n is not a multiple of 4, you can always win by removing enough stones to leave a multiple of 4 for your opponent. For example, if n % 4 == 1, take 1 stone; if n % 4 == 2, take 2 stones; and so on.
3. Implementation: The check is simple: return True if n % 4 != 0, otherwise return False.

Example Walkthrough

Let's walk through an example with n = 7:

• Your turn: There are 7 stones.
• You take 3 stones (leaving 4), or 2 stones (leaving 5), or 1 stone (leaving 6). Let's say you take 3 (leaving 4).
• Opponent's turn: 4 stones left. No matter what they do, you will win on your next turn:
  • If they take 1, 3 left for you (you take all 3 and win).
  • If they take 2, 2 left for you (you take both and win).
  • If they take 3, 1 left for you (you take the last and win).
• So, as long as you don't start with a multiple of 4, you can always force a win by leaving your opponent with a multiple of 4 on every turn.

Time and Space Complexity

Brute-force approach:

• Would require simulating every move for every possible number of stones, leading to exponential time complexity: O(3ⁿ).
• Space complexity would also be high due to recursion stack or memoization.

• Time complexity: O(1), since we only need to compute n % 4 and compare it to 0.
• Space complexity: O(1), as no additional data structures are needed.

Summary

The Nim Game problem demonstrates how a simple mathematical insight can replace brute-force simulation. By recognizing that multiples of 4 are losing positions, we can solve the problem in constant time and space. The elegance of this solution lies in its simplicity and the power of pattern recognition in combinatorial games.