【LeetCode】 292. Nim Game

Description

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:

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.

Solution

• 當石頭為1~3顆，你可以直接拿光，你贏了。
• 當石頭為4顆，你不管拿幾顆，對手都可以拿光，你輸了。
• 當石頭為5~7顆，你都可以拿到剩4顆，你贏了。
• 當石頭為8顆，不管你拿幾顆，對手都可以拿到剩4顆，你輸了。
• 你可以發現，當石頭為4的倍數的時候，你會輸，反之則贏。

Code

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

tags: LeetCode C++