Nim Game (C++)

Problem

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.

Analysis

We define the two players as first mover (Player A) and second mover (Player B). Let's break down the stones number and figure out who is going to win at last.
Let's put in mind that the two players are same clever and both have the optimal strategies for the game. So basically two players are equal. A strategy for Player A to win will also make Player B to win if Player B makes the first move.
1. stones 1 ~ 3: Player A will win
2. stones 4: no matter how many stones (1 ~ 3) Player A moves, the left stones turn the Player B in situation as above in case 1 and Player B will win.
3. stones 5 ~ 7: Player A has a strategy to move 1 ~ 3 stones and the left stones turn Player B in situation as above in case 2 and Player A will win.
4. stones 8: no matter how many stones (1 ~ 3) Player A moves, the left stones turn the Player B in situation as above in case 3 and Player B will win.
and so forth.
Corner cases: stones 0: no one wins since no one gets the last move.

Strategy

N is the count of the stones. If N mod 4 = 0, first mover will lose the game. Otherwise, first mover always move the stones of N mod 4.

Time complexity

O(1)

C++ code

1 2 3 4 5 6 7 8 9

class Solution { public: bool canWinNim(int n) { if (n <= 0) return false; if (n % 4 == 0) return false; return true; } };