## 题目描述

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.

## 解法一

### 思路

• 题目描述里已经提示了，谁碰到还剩1、2或3颗石子的时候就一定会赢，因为肯定会一口气拿完。
• 现在考虑还剩4颗石子的时候，这时自己最少要拿1颗，最多能拿3颗，这样留给对手的一定是[1, 3]颗石子，这样对手一定赢。
• 再来考虑还剩5颗的时候，留给对手的可以是[2, 4]颗石子，显然只能是留4颗石子给对手才能确保自己赢；剩6颗、7颗也是一样的道理。
• 再看剩8颗的情况，与[5, 7]颗不同的是，现在留给对手的只能是[5, 7]，而根据上一步的分析这样对手一定赢。

### Python

``````class Solution(object):
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
return n % 4 != 0``````

### Java

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

### C++

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