Nim Game

Problem: Two players are playing the following Nim Game:

• Initially, there is a heap of stones on the table.
• Both players will alternate taking turns, and Player 1 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 Player (1) who started the game, can win the game assuming both players play optimally, otherwise return false.

Example:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. P1 removes 1 stone. P2 removes all the remaining (4 - 1 =) 3 stones. P2 wins.
2. P1 removes 2 stones. P2 removes all the remaining (4 - 2 =) 2 stones. P2 wins.
3. P1 removes 3 stones. P2 removes the last (4 - 3 =) 1 stone. P2 wins.
In all outcomes, P2 wins.

Approach: If you look at the above example closely, you will understand Player 2 will only win if n is a multiple of 4. Otherwise Player 1 can always win as he/she can always leave 4 stones on the table in the second last turn.

Implementation in C#:

        public bool CanWinNim(int n) 

        {

            return n % 4 != 0;

        }

Complexity: O(1)