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

Example

Input: 4
Output: false
Explanation: 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个石头时候，那么先手一定会输。 对于5个石头来说的话，先手可以通过拿1个时候，把剩下4个石头的这个情况留给对方来使得自己获胜。 6，7这两种情况和 5 是一样的。而8个石头的情况和4个石头的情况是一样的。 那么我们可以发现只要是4的整数倍。先手都会输掉。

代码

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