Divisor Game: Math Pattern Recognition

Alice and Bob take turns playing a game. Alice goes first. They start with a number n on the board. On each turn, the current player chooses any x such that 0 < x < n and n % x == 0, then replaces n with n - x. The player who cannot make a move loses. Given n, return true if Alice wins the game, assuming both players play optimally.

This is LeetCode 1025: Divisor Game, and it is one of those problems where the optimal solution is almost suspiciously simple. The trick is recognizing the mathematical pattern hiding behind what looks like a game theory problem.

Why this problem matters

The Divisor Game teaches you to look past the surface complexity of a problem. Your first instinct might be to build a full game tree or a DP table, and those approaches do work. But the real lesson is that sometimes a problem has a clean mathematical invariant that makes all that machinery unnecessary.

Game theory problems show up regularly in interviews and contests. They test whether you can reason about optimal play, which is a skill that transfers to problems like Nim Game, Stone Game, and Can I Win. The core question is always the same: given that both players are perfectly rational, who has the forced win?

This problem is also a great example of how parity (even vs. odd) can simplify analysis. Parity arguments appear across many areas of math and CS, from graph coloring to bit manipulation. Learning to spot them here will help you everywhere.

The key insight

Alice wins if and only if n is even. That is the entire answer. No recursion, no memoization, no game tree. Just check whether n is even.

Here is why. Consider what happens when you subtract a divisor from a number:

• If n is odd, all of its divisors are odd (an odd number cannot have an even divisor). Subtracting an odd divisor from an odd number always gives an even result. So the current player is forced to hand an even number to the opponent.
• If n is even, the number 1 is always a valid divisor. Subtracting 1 from an even number gives an odd result. So the current player can always choose to hand an odd number to the opponent.

This creates an unbreakable cycle. The player with an even number can always push an odd number to the opponent. The player with an odd number is forced to push an even number back. The game ends when someone is stuck with n = 1, which is odd and has no valid move (there is no x where 0 < x < 1).

Since Alice goes first, if n is even she can keep handing Bob odd numbers until he hits 1. If n is odd, she is the one who will eventually be stuck with 1.

The solution

def divisor_game(n):
    return n % 2 == 0

That is it. One line. The function returns true when n is even and false when n is odd.

This works because the parity argument above is a complete proof by induction. The base case is n = 1 (odd, Alice loses) and n = 2 (even, Alice picks x = 1, Bob gets n = 1, Alice wins). The inductive step shows that even always leads to a win and odd always leads to a loss, no matter how large n gets.

Visual walkthrough

The cycle diagram in Step 5 captures the entire proof. Even hands off odd, odd hands off even, and the cycle terminates at n = 1 (odd). Whoever gets stuck with the odd number at the end loses.

Complexity analysis

Time: The math approach is O(1) because it performs a single modulo operation. The DP approach is O(n^2) because for each value from 2 to n, you check all its divisors (up to n divisors in the worst case).

Space: The math approach uses O(1) extra space. The DP approach needs an O(n) array to store whether each game state is a win or a loss.

The building blocks

1. Parity analysis

The core technique here is reasoning about whether numbers are even or odd, and how arithmetic operations change parity. This is a fundamental tool in number theory and combinatorics.

def is_even(n):
    return n % 2 == 0

def parity_after_subtraction(n, x):
    return (n - x) % 2

The key rule: odd minus odd equals even, and even minus odd equals odd. Since all divisors of an odd number are odd, subtracting any divisor from an odd number always produces an even number.

2. DP verification

If you are not confident in the math proof, you can verify it with dynamic programming. Build a table where dp[i] is True if the player whose turn it is (with i on the board) has a winning strategy.

def divisor_game_dp(n):
    dp = [False] * (n + 1)
    for i in range(2, n + 1):
        for x in range(1, i):
            if i % x == 0 and not dp[i - x]:
                dp[i] = True
                break
    return dp[n]

A position is a win if there exists any move that leaves the opponent in a losing position. Running this for any n confirms the pattern: every even index is True, every odd index is False.

Edge cases

• n = 1: Alice cannot move (no valid x). Return false.
• n = 2: Alice picks x = 1, Bob gets n = 1 and loses. Return true.
• n = 3: Alice must pick x = 1 (only divisor less than 3). Bob gets n = 2 and wins. Return false.
• Large even n: Alice always has a winning strategy regardless of how large n is, as long as it is even.
• Large odd n: Even with many divisors (like n = 999), all divisors of an odd number are odd, so Alice is forced to give Bob an even number.

From understanding to recall

The Divisor Game has one of the cleanest solutions in all of LeetCode, but that simplicity can be deceptive. It is easy to read return n % 2 == 0 and think you understand the problem. The real challenge is being able to derive that solution from scratch, starting from the game rules and arriving at the parity argument on your own.

Spaced repetition helps you internalize the reasoning process, not just the final answer. Each time you revisit this problem, you practice the chain of logic: odd numbers only have odd divisors, odd minus odd is even, even numbers can always subtract 1 to produce odd, and the cycle terminates at n = 1. After a few repetitions, that reasoning becomes automatic.

Parity analysis is a building block that appears in many other problems. The Nim Game uses a similar invariant (multiples of a certain number). Stone Game problems often reduce to parity or symmetry arguments. By drilling these patterns through spaced repetition, you build a toolkit of proof techniques that transfer across problems.

Related posts

• Nim Game - another game theory problem where the winner depends on a mathematical invariant
• Climbing Stairs - simple DP with mathematical insight, another Fibonacci-style pattern
• Power of Two - bit manipulation and parity reasoning

If you want to stop re-solving problems you have already cracked and start building permanent intuition for patterns like parity analysis and game theory, give spaced repetition a try. It is the fastest way to turn understanding into recall.