# LeetCode Nim Game

LeetCode 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.

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?

• 如果n∈[1,3]，则我第一次拿就可以把所有石头拿走，所以我肯定可以获胜。
• 如果n=4，则无论我第一次拿多少个，因为我最多可以拿3个，所以剩下的石头数转换为了n∈[1,3]的情况，也就是变成了对手肯定能获胜的情况。
• 如果n∈[5,7]，则我为了获胜，可以想方设法让我第一次拿了之后，剩余4个石头，这样相当于对手遇到n=4的情况，于是转换为我可以获胜的情况。
• 如果n=8，则无论第一次拿多少个，剩余的石头个数都转换为了n∈[5,7]的情况，也就变成了对手必胜的情况。
• ...

```class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};
```