Nim Game

easy math brainteaser game theory

Problem

You and a friend take turns removing 1, 2, or 3 stones from a heap of n. The player to take the last stone wins. Both play optimally. Return true if you (going first) can win.

Inputn = 4

Outputfalse

Whatever you take (1/2/3), opponent takes the rest. Multiples of 4 are losing for the player about to move.

def can_win_nim(n):
    return n % 4 != 0

function canWinNim(n) {
  return n % 4 !== 0;
}

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

bool canWinNim(int n) {
    return n % 4 != 0;
}

Explanation

This looks like a game you would have to simulate, but it collapses to a one-line rule: you win unless the heap size is a multiple of 4. The whole solution is just n % 4 != 0.

The key insight is about multiples of 4. Whatever you remove on your turn (1, 2, or 3 stones), your opponent can always remove enough to bring the total taken in that round back up to exactly 4. So if the pile starts as a multiple of 4, your opponent can keep restoring that property and will take the last stone.

If the pile is not a multiple of 4, you simply take n % 4 stones on your first move. That leaves a clean multiple of 4 for your opponent, and now they are in the losing position — you mirror their moves from then on.

Example: n = 4. Any move leaves 1, 2, or 3 stones, all of which the opponent takes to win, so you lose and the answer is false. For n = 5, you take 1 to leave 4, and now you win.

Since it is a single modulo check, this runs in constant time and space.

Time: O(1) Space: O(1)