Game Theory (Nim & Grundy)

Game theory in interviews almost always means one specific family: impartial games like Nim, where both players have the same moves available and the only thing that matters is the position. The astonishing result is that an entire game of Nim — any number of piles, any sizes — is decided by a single number: the XOR of all the pile sizes, called the nim-sum.

The deeper machinery is Grundy numbers (the Sprague–Grundy theorem): every impartial game position has a value, its Grundy number, and a sum of independent games behaves like Nim where each pile size is replaced by that game's Grundy number. Plain Nim is the special case where a pile of size n already has Grundy number n.

Intuition

Why XOR? Think of each pile size in binary and stack the numbers in columns. The nim-sum is non-zero when some bit column has an odd number of 1s. The player to move can always flip that imbalance: pick a pile that has a 1 in the highest unbalanced column and shrink it so that every column becomes even again — leaving a nim-sum of 0.

Their opponent now faces an all-zero nim-sum. Any move they make must change exactly one pile, which flips at least one bit column back to odd — handing a non-zero nim-sum (a winning position) straight back to you. So 0 is the "losing" position you keep forcing your opponent into, all the way down to the empty board.

Walk through it

Step through the animation on the right. The piles row holds [3, 4, 5], and the nim-sum label below tracks the running XOR.

The p pointer visits each pile in turn and XORs its size into the nim-sum: 0 ^ 3 = 3, then 3 ^ 4 = 7, then 7 ^ 5 = 2. The final nim-sum is 2, which is non-zero, so the verdict is first player wins.

Now find the winning move. For each pile compute p ^ nim_sum = p ^ 2. Pile 0 (size 3) gives 3 ^ 2 = 1, and 1 < 3, so it is a legal move: reduce that pile from 3 to 1. After the move the piles are [1, 4, 5] with nim-sum 1 ^ 4 ^ 5 = 0 — the opponent is now stuck in a losing position.

The code, line by line

def nim_first_player_wins(piles):
    nim_sum = 0
    for p in piles:
        nim_sum ^= p
    if nim_sum == 0:
        return None            # first player loses
    for i, p in enumerate(piles):
        target = p ^ nim_sum   # desired new size
        if target < p:
            return (i, target) # reduce pile i to target

• Lines 2–4 fold the piles together with XOR. Order does not matter — XOR is commutative and associative — so this is a single clean pass.
• Line 5 is the verdict: a nim-sum of 0 means every move you make worsens your position, so the player to move loses. We return None.
• Line 8 computes the target size for each pile: p ^ nim_sum. XOR-ing the whole sum into one pile is exactly what cancels every unbalanced bit column.
• Line 9 checks target < p — only a smaller target is a legal Nim move (you can only remove stones). The first pile that qualifies is a winning move, returned as (index, new_size).

Complexity

Everything is a handful of integer XORs over the n piles, using only a single accumulator — so time is O(n) and extra space is O(1). There is no search tree to explore: the XOR theorem collapses what looks like an exponential game analysis into one linear scan.

When to use / pitfalls

Practice