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 ith 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: 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.length1 <= n <= 71 <= 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.
Solutions
Solution 1
PythonJavaC++GoTypeScript
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))(code-box)
class Solution {
private Map<Integer, Boolean> memo = new HashMap<>();
private int[] p = new int[8];
public Solution() {
p[0] = 1;
for (int i = 1; i < 8; ++i) {
p[i] = p[i - 1] * 8;
}
}
public boolean nimGame(int[] piles) {
return dfs(piles);
}
private boolean dfs(int[] piles) {
int st = f(piles);
if (memo.containsKey(st)) {
return memo.get(st);
}
for (int i = 0; i < piles.length; ++i) {
for (int j = 1; j <= piles[i]; ++j) {
piles[i] -= j;
if (!dfs(piles)) {
piles[i] += j;
memo.put(st, true);
return true;
}
piles[i] += j;
}
}
memo.put(st, false);
return false;
}
private int f(int[] piles) {
int st = 0;
for (int i = 0; i < piles.length; ++i) {
st += piles[i] * p[i];
}
return st;
}
}(code-box)
class Solution {
public:
bool nimGame(vector<int>& piles) {
unordered_map<int, int> memo;
int p[8] = {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);
}
};(code-box)
func nimGame(piles []int) bool {
memo := map[int]bool{}
p := make([]int, 8)
p[0] = 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)
}(code-box)
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);
}(code-box)
