Nim Game

Problem#

You and an opponent alternately remove 1, 2, or 3 stones from a pile of n. The player who takes the last stone wins. You go first. Return true iff you can guarantee a win with optimal play.

Examples#

• n=1 → true; n=2 → true; n=3 → true; n=4 → false.
• n=7 → true (take 3, leaving 4 — a losing position for the opponent).

Constraints#

• 1 <= n <= 2^31 - 1.

Approach#

If n % 4 == 0, you always face a multiple of 4 after your move plus the opponent’s response (sum is 4); so opponent maintains the bad position. If not, take n % 4 and dump the rest of the work on the opponent.

Solution#

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

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

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

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

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

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

Editorial#

Classic Sprague-Grundy result: in this game, positions with pile size divisible by 4 are losing (P-positions) for the player to move. The invariant is that no matter what the current player takes (1, 2, or 3), the opponent can take 4 - that to restore divisibility by 4.

Complexity#

• Time: O(1).
• Space: O(1).

Concept revision#

Related#

• Bulb Switcher