LeetCode 1025 - Divisor Game

The problem describes a two-player turn-based game between Alice and Bob. The game starts with a single integer n written on a chalkboard. Alice always takes the first turn.

leetcodeeasymathdynamic-programmingbrainteasergame-theory

LeetCode Problem 1025

Difficulty: 🟢 Easy
Topics: Math, Dynamic Programming, Brainteaser, Game Theory

Solution

Problem Understanding

The problem describes a two-player turn-based game between Alice and Bob. The game starts with a single integer n written on a chalkboard. Alice always takes the first turn.

On each turn, the current player must choose a positive integer x such that:

  • 0 < x < n
  • x divides n evenly, meaning n % x == 0

After choosing x, the player replaces the current number n with n - x.

The game continues until a player cannot make a valid move. A player who cannot move loses immediately.

The goal is to determine whether Alice can guarantee a win if both players play optimally. "Optimally" means each player always makes the best possible move to maximize their own chance of winning.

The input consists of a single integer n, where:

1 <= n <= 1000

This constraint is relatively small, which means even simulation or dynamic programming approaches are feasible. However, the problem is labeled as a math and game theory problem because there is a much simpler observation that leads to a constant-time solution.

The output is a boolean value:

  • true if Alice can force a win
  • false otherwise

Several edge cases are important to consider immediately.

When n = 1, Alice has no valid move because there is no integer x satisfying 0 < x < 1. Therefore, Alice loses immediately.

When n = 2, Alice can choose x = 1, leaving Bob with 1. Bob then has no valid moves, so Alice wins.

Another important observation involves parity. Since divisors and subtraction affect whether the resulting number is even or odd, understanding parity transitions becomes the key to solving the problem efficiently.

Approaches

Brute Force Approach

A straightforward approach is to simulate all possible game states recursively.

For every current value of n, we try every valid divisor x. After choosing x, the game moves to state n - x. If there exists at least one move that causes the opponent to lose, then the current state is winning.

This naturally leads to recursive game-state exploration:

  • A state is winning if at least one next state is losing
  • A state is losing if all next states are winning

For example:

  • n = 1 is losing because there are no valid moves
  • n = 2 is winning because choosing 1 leaves 1, which is losing
  • n = 3 is losing because the only move leads to 2, which is winning

Without memoization, this recursive solution repeatedly recomputes the same states and becomes inefficient.

With memoization or dynamic programming, the complexity becomes manageable for n <= 1000, but the solution is still more complicated than necessary.

Key Insight

The crucial observation is that the answer depends entirely on whether n is even or odd.

If n is even, Alice can always force a win.

If n is odd, Alice will always lose.

Why?

Every divisor of an odd number is also odd. If Alice starts with an odd number:

  • She must subtract an odd divisor
  • Odd minus odd equals even
  • Therefore, she always gives Bob an even number

Now consider an even number:

  • An even number always has divisor 1
  • Subtracting 1 from an even number produces an odd number
  • Therefore, the player with an even number can always force the opponent into an odd number

This creates a repeating pattern:

  • Odd numbers are losing states
  • Even numbers are winning states

Since Alice starts first, she wins exactly when n is even.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Recursively explores all valid moves with memoization
Optimal O(1) O(1) Uses parity observation from game theory

Algorithm Walkthrough

Optimal Algorithm

  1. Check whether n is even.

The entire game can be reduced to the parity of n. If n is divisible by 2, Alice can always force the game into an odd state for Bob. 2. Return true if n is even.

An even number guarantees a winning strategy because Alice can always subtract 1, which is a valid divisor of every integer. 3. Return false if n is odd.

An odd number guarantees a losing position because every valid divisor is odd, meaning the resulting value will always become even for the opponent.

Why it works

The invariant is that every even number is a winning state and every odd number is a losing state.

This can be proven inductively:

  • Base case:

  • 1 is losing

  • 2 is winning

  • Inductive step:

  • If n is even, subtract 1 to give the opponent an odd number

  • If n is odd, every divisor is odd, so every move gives the opponent an even number

Thus, optimal play guarantees that the player who receives an odd number eventually loses.

Python Solution

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

The implementation is extremely compact because the mathematical observation completely eliminates the need for recursion or dynamic programming.

The expression n % 2 == 0 checks whether n is even.

  • If the result is True, Alice wins.
  • If the result is False, Alice loses.

This directly encodes the proven game theory result derived in the algorithm walkthrough.

Go Solution

func divisorGame(n int) bool {
    return n%2 == 0
}

The Go implementation is nearly identical to the Python version.

Go uses the % operator for modulo operations exactly like Python. Since the constraints are very small, integer overflow is not a concern.

No additional memory structures are required, and the function immediately returns the parity check result.

Worked Examples

Example 1

Input: n = 2
Output: true

Alice starts with 2.

Turn Current n Valid Moves Chosen Move Resulting n
Alice 2 1 1 1
Bob 1 none none loses

Bob cannot make a move, so Alice wins.

The algorithm checks:

2 % 2 == 0

Result:

True

Example 2

Input: n = 3
Output: false

Alice starts with 3.

The only valid divisor smaller than 3 is 1.

Turn Current n Valid Moves Chosen Move Resulting n
Alice 3 1 1 2
Bob 2 1 1 1
Alice 1 none none loses

Alice loses because she eventually receives 1.

The algorithm checks:

3 % 2 == 0

Result:

False

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only a single modulo operation is performed
Space O(1) No extra memory is used

The solution runs in constant time because it does not iterate, recurse, or allocate additional data structures. The result depends solely on whether n is even or odd.

Test Cases

solution = Solution()

assert solution.divisorGame(1) == False  # smallest input, no moves possible
assert solution.divisorGame(2) == True   # simplest winning case
assert solution.divisorGame(3) == False  # simplest losing odd number
assert solution.divisorGame(4) == True   # even number should always win
assert solution.divisorGame(5) == False  # odd number should always lose
assert solution.divisorGame(6) == True   # larger even number
assert solution.divisorGame(7) == False  # larger odd number
assert solution.divisorGame(8) == True   # repeated even validation
assert solution.divisorGame(999) == False  # largest odd near constraint
assert solution.divisorGame(1000) == True # upper constraint boundary
Test Why
n = 1 Verifies no valid moves case
n = 2 Smallest winning state
n = 3 Smallest losing odd state
n = 4 Confirms even-number strategy
n = 5 Confirms odd-number loss
n = 6 Tests larger even value
n = 7 Tests larger odd value
n = 8 Additional parity validation
n = 999 Large odd boundary case
n = 1000 Maximum constraint value

Edge Cases

Edge Case 1: n = 1

This is the smallest possible input and is a losing state immediately. A naive implementation might incorrectly assume every number has at least one divisor smaller than itself.

In this case, there is no valid x satisfying:

0 < x < 1

Therefore, Alice loses immediately. The implementation handles this correctly because:

1 % 2 == 1

which returns False.

Edge Case 2: Small Even Numbers

Values like 2 and 4 are important because they demonstrate the core winning strategy.

For 2, Alice subtracts 1 and wins instantly.

For 4, Alice can subtract 1 to leave 3, which is a losing state.

A buggy recursive implementation might fail to classify these base cases correctly. The parity-based solution avoids this issue entirely.

Edge Case 3: Large Odd Numbers

Large odd numbers such as 999 may appear difficult because they have many divisors.

However, every divisor of an odd number is also odd. Subtracting any odd divisor from an odd number always produces an even number.

Therefore, regardless of the move chosen, the current player always hands an even number to the opponent, which is a winning state for the opponent.

The implementation handles all odd numbers uniformly with a single parity check.