Nim Game Solutions in C++

// Source : https://leetcode.com/problems/nim-game/
// Author : Calinescu Valentin
// Date   : 2015-10-19





/* 
 * Solutions
 * =========
 *
 * Let's look at the example:
 * 
 *    0 stones - false
 *    1 stone - true
 *    2 stones - true
 *    3 stones - true
 *    4 stones - false
 * 
 * We notice that all we need for a position to be true is to get the opponent in a position 
 * that is false. With 1, 2 and 3 you can take 1, 2 and 3 stones respectively to force your 
 * opponent into having 0 stones, a position where he cannot win. No matter how many stones 
 * we take from 4 we cannot 
 *
 * force the opponent into a losing positon, so position 4 becomes a losing position. 
 * Let's take a look at the next 4 positions:
 * 
 *     5 stones - true
 *     6 stones - true
 *     7 stones - true
 *     8 stones - false
 * 
 * With 5, 6 and 7 stones we can take 1, 2 and 3 stones respectively to force the opponent into 
 * position 4. Position 8 is a losing one because we can only force the opponent into winning 
 * positions. We notice that this group of 4 positions can repeat itself indefinitely, because 
 * we only need the previous 3 positions to judge whether a position is winning or losing. 
 *
 * Thus we can see the pattern:
 * 
 *     n % 4 == 0 - false
 *     n % 4 != 0 - true
 * 
 */

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