Nim Game

Problem Statement

In the Nim Game, you face off against a friend as you alternatively take turns removing stones from a single heap. From this heap, each player can remove 1 to 3 stones during their turn. The game starts with you making the first move, and the objective is to be the player who removes the last stone from the heap. Given n, representing the total number of stones in the heap at the start, the challenge lies in determining whether you can guarantee a win if both players employ their best strategies. Your solution should provide a boolean answer of true if a win is certain for you with optimal play, otherwise it should return false.

Examples

Example 1

Input:

n = 4

Output:

false

Explanation:

These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2

Input:

n = 1

Output:

true

Example 3

Input:

n = 2

Output:

true

Constraints

• 1 <= n <= 231 - 1

Approach and Intuition

To determine if you can win the Nim Game given n stones, where optimal strategies are employed by both players:

1. Observe the impact of the game setup:

   • Having multiples of 4 stones in the heap (n % 4 == 0) puts the first player at a disadvantage. This is because any move the first player makes will leave a non-multiple of 4, which the second player can always return to a multiple of 4, trapping the first player in a cycle where they must always face a heap that is again a multiple of 4 when their turn comes around next.

2. General behavior based on n:

   • For n = 1, 2, or 3: The first player can immediately remove all stones and win, therefore, the function returns true.

   • For n = 4: No matter the strategy, the first player's move will result in a scenario where their friend can always remove the remaining stones, leading to a guaranteed loss for the first player. Hence, the result is false.

   • For n > 4: The game links back to the analysis of multiples of 4. If n is a multiple of 4, then the first player will lose with optimal play by the second. If n is not a multiple of 4, the first player can always adjust their move to force the total number of stones left to become a multiple of 4 for their friend's turn, guiding them towards a structured win.

Given these points, the solution involves checking if the number of stones n modulo 4 equals 0. If it does, return false; otherwise, return true. This method leverages the mathematical properties of the game rather than simulating each possibility, offering an optimal decision-making strategy.

Solutions

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