Nim Game — Editorial

Opening the reading…

Intuitionwhy multiples of four are the losing positions

Start with the smallest positions. With 1, 2, or 3 stones, you take all the stones and win. With 4 stones, every move leaves 3, 2, or 1 stones for your opponent, and your opponent takes the rest. Therefore 4 is losing, while 1, 2, and 3 are winning positions.

The same idea repeats after every four stones. If you leave your opponent a multiple of 4, then whatever they remove, from 1 to 3, you remove the complementary number so the two moves remove exactly 4 stones. Starting from a non-multiple of 4, remove its remainder: 1, 2, or 3 stones. Starting from a multiple of 4, every first move gives the opponent a winning non-multiple.

Approachreduce the game to its repeating losing pattern

Check n modulo 4, because positions separated by four stones have the same strategic outcome and the remainder identifies how many stones are needed for the first move.

Return true when n % 4 is not zero, because the first player can remove that remainder and leave a multiple of 4 to the opponent.

Return false when n % 4 is zero, because every legal first move leaves 1, 2, or 3 modulo 4 stones, which is a winning position for the next player.

Do not simulate later turns, because after the first player leaves a multiple of 4, the opponent's move already determines the complementary response that restores a multiple of 4.

Complexityconstant work and no game state

MEASURE	BOUND	WHY
Time	O(1)	The solution performs one remainder operation and one comparison, regardless of how large n is; it does not visit individual stones or game states.
Space	O(1) extra	Only the input value and a boolean result are used. The returned boolean is required output and is excluded from the extra-space bound, which remains constant for every valid input.

Annotated solutionC++ · direct modular characterization

CPPReturn whether the stone count is outside the repeating losing class of multiples of four.

#include <iostream>
using namespace std;

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

The entire proof is captured by the comparison n % 4 != 0. A remainder of 1, 2, or 3 tells you exactly how many stones to remove first. A remainder of 0 means no legal move can leave another multiple of 4, so the opponent can make the complementary response after every turn.