(LeetCode OJ) Nim Game【292】

(LeetCode OJ) Nim Game【292】

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:

    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?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
Show Similar Problems

    //思路首先：將問題規模縮小，找規律：  
    //桌子上只有1個我必贏，2個我必贏，3個我必贏，4個我必輸，5個我必贏，6個必贏，7個必贏  
    //8個，就是兩個4，我第一輪無論怎麼摸石頭都能讓對手最後（以4為一個坎）摸完石頭，所以必輸  
    //也就是說n%4==0必輸了哦？最後試了一下，的確是這樣的。  
    class Solution {  
    public:  
        bool canWinNim(int n) {  
            return n%4!=0;//臥槽，此題代碼可以如此簡單，意義何在？  
        }  
    };