Nim Game

Problem

You are playing the following Nim Game with your friend:

• Initially, there is a heap of stones on the table.
• You and your friend will alternate taking turns, and you go first.
• On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
• The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

Constraints

• 1 <= n <= 231 - 1

Solution

The problem Nim Game can be solved by checking if a given number is divisible by 4. If a given number is α + 4 * n where 1 <= α <= 3, n = 0, 1, 2, 3, ..., then the game can always be won by first taking α number of stones and then taking 4 - β stones every time oppenent takes β stones where 1 <= β <= 3. On the contrary, if there are 4 * n stones, then the opponent can always take the last stone by taking 4 - α stones for every α stones taken where 1 <= α <= 3.

Implementation

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