Formatted question description: https://leetcode.ca/all/1908.html

1908. Game of Nim

Level

Medium

Description

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 i-th pile, return true if Alice wins, or false if Bob wins.

Both Alice and Bob play optimally.

Example 1:

Input: piles = [1]

Output: true

*Explanation:8 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?

Solution

For the game of Nim, where Alice starts first, Alice can win if and only if the bitwise xor results of all the elements in piles is not 0.

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

All Problems

All Solutions