leetCode Question: Nim Game

Nim Game

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.

Analysis:

Let's first simulate the game with a small number of stones, say 4. We will take the first turn to remove the stones.

If there are 4 stones, we have three options, take 1, 2 or 3 stones:
We take 1, 3 left
We take 2, 2 left
We take 3, 1 left

Then it's opponent's turn, assume he is doing his best to win the game:
We take 1, 3 left, opponent take 3, opponent win, we lose
We take 2, 2 left, opponent take 2, opponent win, we lose
We take 3, 1 left, opponent take 1, opponent win, we lose

Note that, if it is our turn and there are n stones, say it is a must-win, then for the opponent facing n stones, it is a must-win for the opponent, and for us it becomes a must-lose case.

What about 5 stones:
We take 3, 2 left, opponent take 2, opponent win, we lose
We take 2, 3 left, opponent take 3, opponent win, we lose

We take 1, 4 left, now opponent has 3 options:

• opponent take 1, 3 left, then we take 3, we win, opponent lose
• opponent take 2, 2 left, then we take 2, we win, opponent lose
• opponent take 3, 1 left, then we take 1, we win, opponent lose

From this observation, we could see that:

• We have to make the number of stones to 4 after our pick, so that opponent must lose and we must win.
• There are 3 possibilities: when there are 4+1=5, 4+2=6 or 4+3=7 stones, we could make it 4 after we pick 1, 2 and 3 stones, respectively.
• If the number of stones is times of 4, we will never win the game. Say there are 16 stones, we choose n stones, no matter how we choose, the opponent could always pick 4-n stones to make the number of stones still times of 4, until we met 4 stones, and we will lose.

Therefore, when the number is times of 4, it is a lose, otherwise it is a win.

Code (C++):

class Solution {

public:

bool canWinNim(int n) {

return !(n%4==0);

}

};

Code (Python):

class Solution(object):

def canWinNim(self, n):

"""

:type n: int

:rtype: bool

"""

return not n%4==0