Game of Nim

Problem

Alice and Bob take turns playing a game with Alice starting first.

In this game, there are n piles of stones. On each player's turn, the player should remove any positive number of stones from a non-empty pile of his or her choice. The first player who cannot make a move loses, and the other player wins.

Given an integer array piles, where piles[i] is the number of stones in the ith pile, return true if Alice wins, orfalse if Bob wins.

Both Alice and Bob play optimally.

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

Follow-up: Could you find a linear time solution? Although the linear time solution may be beyond the scope of an interview, it could be interesting to know.

Solution

Method 1 – Bitwise XOR (Nim Game Theorem)

Intuition

The classic Nim game is solved using the XOR of all pile sizes. If the XOR is zero, the current player loses (Bob wins); otherwise, the current player wins (Alice wins). This is because XOR encodes the parity of the game state, and any nonzero XOR means the first player can always force a win with optimal play.

Approach

1. Initialize a variable ans to 0.
2. For each pile, XOR its size with ans.
3. If the final ans is not zero, Alice wins; otherwise, Bob wins.

Code

C++

class Solution {
public:
    bool nimGame(vector<int>& piles) {
        int ans = 0;
        for (int x : piles) ans ^= x;
        return ans != 0;
    }
};

Go

type Solution struct{}
func (Solution) nimGame(piles []int) bool {
    ans := 0
    for _, x := range piles {
        ans ^= x
    }
    return ans != 0
}

Java

class Solution {
    public boolean nimGame(int[] piles) {
        int ans = 0;
        for (int x : piles) ans ^= x;
        return ans != 0;
    }
}

Kotlin

class Solution {
    fun nimGame(piles: IntArray): Boolean {
        var ans = 0
        for (x in piles) ans = ans xor x
        return ans != 0
    }
}

Python

class Solution:
    def nimGame(self, piles: list[int]) -> bool:
        ans = 0
        for x in piles:
            ans ^= x
        return ans != 0

Rust

impl Solution {
    pub fn nim_game(piles: Vec<i32>) -> bool {
        piles.iter().fold(0, |ans, &x| ans ^ x) != 0
    }
}

TypeScript

class Solution {
  nimGame(piles: number[]): boolean {
    let ans = 0;
    for (const x of piles) ans ^= x;
    return ans !== 0;
  }
}

Complexity

• ⏰ Time complexity: O(n), where n is the number of piles, since each pile is processed once.
• 🧺 Space complexity: O(1), as only a few variables are used.