Vultr DocsLatest Content

Game of Nim

Updated on 30 May, 2025
Game of Nim header image

Problem Statement

Alice and Bob are engaged in a turn-based game involving n different piles of stones, with Alice making the initial move. The game's rules are straightforward: during a player's turn, they must select any non-empty pile and remove at least one stone from it. The player faced with empty piles on their turn automatically loses the game. The objective is to determine the winner when both participants play optimally. The game setup is defined by an array piles, where piles[i] specifies the stone count in the i-th pile. The function must return true if Alice wins under optimal conditions and false if Bob wins.

Examples

Example 1

Input:

piles = [1]

Output:

true

Explanation:

There is only one possible scenario:
- On the first turn, Alice removes one stone from the first pile. piles = [0].
- On the second turn, there are no stones left for Bob to remove. Alice wins.

Example 2

Input:

piles = [1,1]

Output:

false

Explanation:

It can be proven that Bob will always win. One possible scenario is:
- On the first turn, Alice removes one stone from the first pile. piles = [0,1].
- On the second turn, Bob removes one stone from the second pile. piles = [0,0].
- On the third turn, there are no stones left for Alice to remove. Bob wins.

Example 3

Input:

piles = [1,2,3]

Output:

false

Explanation:

It can be proven that Bob will always win. One possible scenario is:
- On the first turn, Alice removes three stones from the third pile. piles = [1,2,0].
- On the second turn, Bob removes one stone from the second pile. piles = [1,1,0].
- On the third turn, Alice removes one stone from the first pile. piles = [0,1,0].
- On the fourth turn, Bob removes one stone from the second pile. piles = [0,0,0].
- On the fifth turn, there are no stones left for Alice to remove. Bob wins.

Constraints

  • n == piles.length
  • 1 <= n <= 7
  • 1 <= piles[i] <= 7

Approach and Intuition

Given the competitive nature of the game, a thorough understanding of the examples and constraints can provide significant insights into forming a winning strategy or predicting the outcome.

Scenario Examination

  1. Example Single Pile (piles = [1]):

    • Alice removes the only stone. Bob has no moves left, ensuring Alice wins.

  2. Example Twin Piles (piles = [1,1]):

    • Alice removes a stone from one pile, and then Bob does the same for the other pile. Alice, now without a move, loses. Bob’s strategy to mirror Alice's actions leads him to victory.

  3. Example Mixed Piles (piles = [1,2,3]):

    • A more complex scenario shows a continuation of turns, where each optimal move leads to Bob's victory as he strategically ensures that Alice is left with no moves.

Key Observations:

  • Game Dynamics: The game's nature changes significantly with the even or odd aggregate of stones. It's notable how the turn dynamics and strategic removals can transform the prospects dramatically.
  • Optimal Play: Both players aim to reduce the game to a state where the opponent has the least favorable position, adhering strictly to removing stones in a manner that maximizes their chance of winning under any scenario.

By exploring these examples, one can observe that the task isn't merely about removing stones, but about maintaining control over the game's pace and strategically compelling the opponent into a non-viable position by the end of their turn.

Solutions

  • Java
  • JavaScript
  • Python
java 
class Solution {
    public boolean playNimGame(int[] stones) {
        int totalXOR = 0;
        for (int stoneCount : stones) {
            totalXOR ^= stoneCount;
        }
        return totalXOR != 0;
    }
}

This solution implements the classic problem known as the "Game of Nim" using Java. In this game, the function playNimGame receives an array stones, where each element represents the count of stones in each pile.

To determine the winner under the optimal strategies for both players, utilize the XOR operation. XOR all elements of the stones array sequentially. The result stored in totalXOR will be analyzed to decide the outcome:

  • If totalXOR equals zero, it indicates a losing position, so the function returns false.
  • If totalXOR is non-zero, the current player can force a win, making the function return true.

This method effectively evaluates the winnability of a Nim game state using bitwise operations, providing a quick and efficient solution.

js 
function calculateNim(pileArray) {
    let result = 0;
    for (let pile of pileArray) {
        result ^= pile;
    }
    return result !== 0;
}

The "Game of Nim" solution provided is implemented in JavaScript. It calculates the winning move based on a given set of piles represented in an array. Review the key aspects of the solution:

  • The function calculateNim accepts an array pileArray, where each integer represents the number of items in a pile.
  • A variable result initializes to zero. This variable accumulates the result of a bitwise XOR operation performed on each pile from the array.
  • Iterate over each pile in pileArray using a for loop. Inside the loop, update result by performing a bitwise XOR (^= operator) of result with the number of items (pile) in the current pile.
  • Finally, the function evaluates whether result is non-zero. If result is non-zero (result !== 0), it returns true, indicating a winning possibility for the player starting the game. Otherwise, it returns false.

The XOR operation is crucial here as it applies the mathematical foundation of the Nim-sum, which determines the winning strategy in the Game of Nim:

  • If the Nim-sum (result) at the beginning of the turn is zero, the player is destined to lose if the opponent plays optimally.
  • Conversely, a non-zero starting Nim-sum allows for a possible winning strategy with optimal play.

Utilize this function by passing an array of integers where each integer counts the items in respective piles, and it will aid in strategizing the next move in the game.

python 
class Solution:
    def canWinNim(self, stones: List[int]) -> bool:
        xor_result = 0
        for stone in stones:
            xor_result ^= stone
        return xor_result != 0

The provided Python solution addresses the problem of determining the winning strategy in the Nim game given an array of integers where each integer represents the number of stones in piles. The solution follows a bit manipulation approach using XOR to determine the outcome:

  • Utilize a loop to iterate through each pile of stones.
  • Accumulate the result of XOR operation on all the piles.
  • Return True if the resultant XOR is not zero, indicating the starting player can ensure a win with optimal play; otherwise, return False.

This method effectively utilizes properties of the XOR operation to evaluate the game state in linear time complexity, making it efficient for handling large inputs. Ensure to include the List import from typing to avoid errors during execution.

Comments