##### Welcome to Subscribe On Youtube

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

# 1908. Game of Nim

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 = 

Output: true

*Explanation:8 There is only one possible scenario:

• On the first turn, Alice removes one stone from the first pile. piles = .
• 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;
}
}

• class Solution {
public:
bool nimGame(vector<int>& piles) {
unordered_map<int, int> memo;
int p = {1};
for (int i = 1; i < 8; ++i) {
p[i] = p[i - 1] * 8;
}
auto f = [&](vector<int>& piles) {
int st = 0;
for (int i = 0; i < piles.size(); ++i) {
st += piles[i] * p[i];
}
return st;
};
function<bool(vector<int>&)> dfs = [&](vector<int>& piles) {
int st = f(piles);
if (memo.count(st)) {
return memo[st];
}
for (int i = 0; i < piles.size(); ++i) {
for (int j = 1; j <= piles[i]; ++j) {
piles[i] -= j;
if (!dfs(piles)) {
piles[i] += j;
return memo[st] = true;
}
piles[i] += j;
}
}
return memo[st] = false;
};
return dfs(piles);
}
};

• class Solution:
def nimGame(self, piles: List[int]) -> bool:
@cache
def dfs(st):
lst = list(st)
for i, x in enumerate(lst):
for j in range(1, x + 1):
lst[i] -= j
if not dfs(tuple(lst)):
return True
lst[i] += j
return False

return dfs(tuple(piles))


• func nimGame(piles []int) bool {
memo := map[int]bool{}
p := make([]int, 8)
p = 1
for i := 1; i < 8; i++ {
p[i] = p[i-1] * 8
}
f := func(piles []int) int {
st := 0
for i, x := range piles {
st += x * p[i]
}
return st
}
var dfs func(piles []int) bool
dfs = func(piles []int) bool {
st := f(piles)
if v, ok := memo[st]; ok {
return v
}
for i, x := range piles {
for j := 1; j <= x; j++ {
piles[i] -= j
if !dfs(piles) {
piles[i] += j
memo[st] = true
return true
}
piles[i] += j
}
}
memo[st] = false
return false
}
return dfs(piles)
}

• function nimGame(piles: number[]): boolean {
const p: number[] = Array(8).fill(1);
for (let i = 1; i < 8; ++i) {
p[i] = p[i - 1] * 8;
}
const f = (piles: number[]): number => {
let st = 0;
for (let i = 0; i < piles.length; ++i) {
st += piles[i] * p[i];
}
return st;
};
const memo: Map<number, boolean> = new Map();
const dfs = (piles: number[]): boolean => {
const st = f(piles);
if (memo.has(st)) {
return memo.get(st)!;
}
for (let i = 0; i < piles.length; ++i) {
for (let j = 1; j <= piles[i]; ++j) {
piles[i] -= j;
if (!dfs(piles)) {
piles[i] += j;
memo.set(st, true);
return true;
}
piles[i] += j;
}
}
memo.set(st, false);
return false;
};
return dfs(piles);
}