292 Nim Game

Problem

292 Nim Game

Solution

Where to begin the thinking?

You should not begin your thinking from the first turn as it is far from the result. Instead, start your thinking from the last turn, because it directly decides whether you can win the Nim Game.

How to ensure you will take the last turn?

• If \(1 \leq stones \leq 3\), you can take all of them and win the game.
• If stones = 4, no matter how many stones you take, the last turn is your opponent, so you will lose if you have 4 stones at your turn.
• If \(5 \leq stones \leq 7\), you can leave 4 stones to your opponent so you will win.
• If stones = 8, no matter how many stones you take, your opponent can always leave you 4 stones so you will lose.

By mathematical induction, we can conclude that the one who has \(4 \times N(N \in Z+)\) stones at his turn will lose the game. It means that you can win the game if and only if the number of stones is not divisible by 4 at your turn.

Code

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