292. Nim Game

  • 54.9%

https://leetcode.com/problems/nim-game/#/description

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

  1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

https://discuss.leetcode.com/topic/26999/theorem-all-4s-shall-be-false

Theorem: all 4s shall be false

Theorem: The first one who got the number that is multiple of 4 (i.e. n % 4 == 0) will lost, otherwise he/she will win.

Proof:

  1. the base case: when n = 4, as suggested by the hint from the problem, no matter which number that that first player, the second player would always be able to pick the remaining number.
  2. For 1 4 < n < 2 4, (n = 5, 6, 7), the first player can reduce the initial number into 4 accordingly, which will leave the death number 4 to the second player. i.e. The numbers 5, 6, 7 are winning numbers for any player who got it first.
  3. Now to the beginning of the next cycle, n = 8, no matter which number that the first player picks, it would always leave the winning numbers (5, 6, 7) to the second player. Therefore, 8 % 4 == 0, again is a death number.
  4. Following the second case, for numbers between (24 = 8) and (34=12), which are 9, 10, 11, are winning numbers for the first player again, because the first player can always reduce the number into the death number 8.

Following the above theorem and proof, the solution could not be simpler:

1
2
3
public boolean canWinNim(int n) {    
return n % 4 != 0 ;
}

https://discuss.leetcode.com/topic/27109/one-line-o-1-solution-and-explanation

One line O(1) solution and explanation

suppose there are x stones left for first player (A), he can take 1,2,3 stones away, so second player B will have three cases to deal with (x -1), (x-2), (x-3). after he pick the stones, there will be 9 cases left for A.

1
2
3
B (x-1) -> A: (x-2), (x-3), (x-4)
B (x-2) -> A: (x-3), (x-4), (x-5)
B (x-3) -> A: (x-4), (x-5), (x-6)

Now, if A can guarantee he win at either of three groups, then he can force B to into that one of the three states and A can end up in that particular group after B’s move.

1
f(x) = (f(x-2)&&f(x-3)&&f(x-4)) || (f(x-3)&&f(x-4)&&f(x-5)) || (f(x-4)&&f(x-5)&&f(x-6))

if we examine the equation a little closer, we can find f(x - 4) is a critical point, if f(x-4) is false, then f(x) will be always false.

we can also find out the initial conditions, f(1), f(2), f(3) will be true (A always win), and f(4) will be false. so

based on previous equation and initial conditions f(5) = f(6) = f(7) = true, f(8) = false;

obviously, f(1), f(2), f(3) can make all f(4n + 1), f(4n + 2), f(4n + 3) to be true, only f(4n) will be false then.

so here we go our one line solution:

1
return (n % 4 != 0);

https://discuss.leetcode.com/topic/28437/1-liner-with-explanations

1 liner with explanations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
# strategy: the one with 4 remaining must loose
# A, B players
# if n == 4k, then at each round B can make A+B both take 4,
# eventually leave 4 to A, A lose
# if n == 4k + i (i <= 3), then A can always take i first and B will
# finanly lose as he faces above scenario like A

return bool(n%4!=0)

https://discuss.leetcode.com/topic/27696/1-line-0-ms-c-solution-with-explanation

1 line 0 ms C++ solution with explanation

Explanation:

At first this problem might seems a bit tough but it is easy and has a pattern which is as follow.

I have applied the bottom up dynamic programming approach to fill the array and noticed that only number divisible by 4 are the positions where player1(playing first chance) is losing.

1
2
3
4
5
6
class Solution {
public:
bool canWinNim(int n) {
return n%4 ;
}
};
  1. Base case :

If the numbers of stones are 1,2 or 3, then player 1 will win.

If the numbers of stones are 4, then player 1 will lose irrespective of the number of stones he/she remove

So lookup table will look like this : W[1]->W[2]->W[3]->L[4].

  1. For num_stones=5, the player can either remove 1,2 or 3 stones i.e. the other player (player 2) will win if the number of stones left are 1,2 or 3 and will lose only when the number of stones left are 4 ( see the lookup table in step 1) .

So, if Player1 remove 1 stone, the number of stones left will be 4, which will defeat player2. So, now the lookup entry for num_stones=5 will be W.

Lookup now will look like this : W->W->W->L->W (for player 1-> who is taking the first chance).

  1. Likewise, we can fill the complete lookup table by looking at the values at last three index. If anyone of them is L => Player 1 will win the game as he will remove only that many number of stones which will bring player 2 to the L position

  2. In the end, you will notice that only positions 4->8->12->16 will contain L for player 1 thus answer is simple n%4.


https://discuss.leetcode.com/topic/30789/if-i-m-a-interviewer-i-prefer-the-candidates-using-burte-force-instead-of-math-method

If I’m a interviewer, I prefer the candidates using burte force instead of math method.

Because it is a “coding interview”, not acm/icpc or other competitions. Similar to Josephus Cycle, I prefer LinkedList Cycle than Mod-Method during interviews. Here’s a backtraking-dp solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
public boolean canWinNim(int n) {
if(n>=134882061){//I have no any other ways,please forgive my unchastity(无节操)!
return n%4 != 0;
}
int[] array=new int[n+1];
return dfs(n, array);
}
public boolean dfs(int n,int[] array){
if(array[n]!=0){
return array[n]==1?true:false;
}
if(n<=3){
array[n]=1;
return true;
}else{
for(int i=1;i<=3;i++){
if(!dfs(n-i,array)){
array[n-i]=-1;
array[n]=1;
return true;
}
}
array[n]=-1;
return false;
}
}
}

谢谢你,可爱的朋友。