LeetCode 1025: Divisor Game

Problem Restatement

Alice and Bob play a game.

They start with the number n.

On each turn, the current player chooses a number x such that:

0 < x < n
n % x == 0

Then n is replaced by n - x.

The player who cannot make a move loses.

Alice always goes first. Both players play optimally.

Return true if Alice wins, false if Bob wins.

The official constraints state that 1 <= n <= 1000.

Input and Output

Function shape:

def divisorGame(n: int) -> bool:
    ...

Examples

Example 1:

n = 2

Alice picks x = 1 (only valid choice). n becomes 1. Bob has no valid move (no x with 0 < x < 1). Alice wins.

Answer:

True

Example 2:

n = 3

Alice must pick x = 1. n becomes 2. Bob picks x = 1. n becomes 1. Alice has no valid move. Bob wins.

Answer:

False

Key Insight

Alice wins if and only if n is even.

Proof by induction:

Base cases:

• n = 1: No valid move for Alice. Alice loses. (Odd → lose.)
• n = 2: Alice picks x = 1, n becomes 1. Bob loses. (Even → win.)

Inductive step:

• If n is odd: any divisor x of an odd number is odd (odd numbers have only odd divisors). So n - x is even. Bob receives an even number and wins by induction. Alice loses.
• If n is even: Alice picks x = 1. n - 1 is odd. Bob receives an odd number and loses by induction. Alice wins.

Algorithm

return n % 2 == 0

Correctness

See the proof above.

For even n:

• Alice plays x = 1, leaving n - 1 (odd) for Bob.
• Bob, receiving an odd number, will eventually lose.

For odd n:

• Any divisor of an odd number is odd.
• n - x is always even (odd minus odd).
• Bob always receives an even number and wins.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0

Code Explanation

The entire logic is a single parity check:

return n % 2 == 0

Even n is a winning position for Alice. Odd n is a losing position.

Alternative: Dynamic Programming

We can also verify this with DP for small n:

class Solution:
    def divisorGame(self, n: int) -> bool:
        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]

This confirms the pattern: dp[i] is True for all even i.

Testing

def run_tests():
    s = Solution()

    assert s.divisorGame(2) == True
    assert s.divisorGame(3) == False
    assert s.divisorGame(1) == False
    assert s.divisorGame(4) == True
    assert s.divisorGame(100) == True
    assert s.divisorGame(999) == False

    print("all tests passed")

run_tests()