Problem Description

Alice and Bob are playing a turn-based game on a chalkboard, with Alice going first.

The game starts with a number n written on the chalkboard. On each turn, a player must:

1. Choose any number x where 0 < x < n and x is a divisor of n (meaning n % x == 0)
2. Replace the number n on the chalkboard with n - x

A player loses if they cannot make a valid move (when no valid x exists).

Your task is to determine whether Alice wins the game, assuming both players play optimally. Return true if Alice wins, false otherwise.

For example:

• If n = 2: Alice can choose x = 1 (since 2 % 1 == 0), leaving Bob with n = 1. Bob has no valid moves, so Alice wins.
• If n = 3: Alice can only choose x = 1 (since 3 % 1 == 0), leaving Bob with n = 2. Bob then chooses x = 1, leaving Alice with n = 1. Alice has no valid moves, so Bob wins.

The solution reveals an elegant pattern: Alice wins if and only if n is even. This can be proven through mathematical induction - when n is odd, all its divisors are odd, so subtracting any divisor leaves an even number for the opponent. When n is even, the current player can always choose x = 1 to leave an odd number for the opponent, ensuring their own victory.

Intuition

Let's think about what happens when we play this game with small values of n:

• n = 1: No valid moves available (no x where 0 < x < 1), so Alice loses immediately.
• n = 2: Alice can take x = 1, leaving Bob with n = 1. Bob loses, Alice wins.
• n = 3: Alice can only take x = 1 (3's only divisor less than 3), leaving Bob with n = 2. From above, we know the player with n = 2 wins, so Bob wins.
• n = 4: Alice could take x = 1 or x = 2. If she takes x = 1, Bob gets n = 3, and we know Bob loses with n = 3. So Alice wins.

A pattern emerges: odd numbers lead to losses, even numbers lead to wins.

Why does this pattern hold? The key insight is about the nature of divisors:

• Odd numbers only have odd divisors (since odd × odd = odd)
• Even numbers have both odd and even divisors

When you have an odd number n, you can only subtract an odd divisor from it. Since odd - odd = even, you're forced to give your opponent an even number.

When you have an even number n, you have a choice. You can subtract 1 (which is always a divisor), giving your opponent n - 1, which is odd. Since the opponent with an odd number is forced to give you back an even number, you maintain control.

This creates a winning strategy: if you start with an even number, always subtract 1 to give your opponent an odd number. They'll be forced to give you back an even number, and this continues until they eventually get stuck with n = 1 and lose.

Therefore, the solution is surprisingly simple: Alice wins if and only if n % 2 == 0.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses mathematical induction to prove that Alice wins when n is even and loses when n is odd.

Base Cases:

• When n = 1: No valid moves exist, so Alice loses.
• When n = 2: Alice takes x = 1, leaving Bob with n = 1. Bob has no moves, so Alice wins.

Inductive Proof: Assume the pattern holds for all values up to k. We need to prove it holds for k + 1:

1. If k + 1 is odd:

   • Any divisor x of an odd number must be odd (since only odd × odd = odd)
   • After Alice's move: (k + 1) - x = odd - odd = even
   • Bob receives an even number
   • By our assumption, the player with an even number wins
   • Therefore, Bob wins and Alice loses

2. If k + 1 is even:

   • Alice can choose x = 1 (1 is always a divisor)
   • After Alice's move: (k + 1) - 1 = even - 1 = odd
   • Bob receives an odd number
   • By our assumption, the player with an odd number loses
   • Therefore, Bob loses and Alice wins

This proves that:

• When n is odd → Alice loses
• When n is even → Alice wins

Implementation: The entire game strategy reduces to a single check:

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

The optimal strategy for the player with an even number is to always subtract 1, forcing the opponent into an odd number position. Since odd numbers can only transition to even numbers, the player who starts with an even number maintains control throughout the game.

Time Complexity: O(1) - just a modulo operation Space Complexity: O(1) - no additional space needed

Example Walkthrough

Let's walk through a game where n = 6 to see how the pattern works:

Initial state: Alice starts with n = 6 (even number)

Alice's turn (n = 6):

• Available divisors of 6 that are less than 6: {1, 2, 3}
• Alice plays optimally and chooses x = 1
• New value: n = 6 - 1 = 5
• Bob receives n = 5 (odd number)

Bob's turn (n = 5):

• Available divisors of 5 that are less than 5: {1} (5 is prime)
• Bob must choose x = 1
• New value: n = 5 - 1 = 4
• Alice receives n = 4 (even number)

Alice's turn (n = 4):

• Available divisors of 4 that are less than 4: {1, 2}
• Alice chooses x = 1 (maintaining the pattern)
• New value: n = 4 - 1 = 3
• Bob receives n = 3 (odd number)

Bob's turn (n = 3):

• Available divisors of 3 that are less than 3: {1}
• Bob must choose x = 1
• New value: n = 3 - 1 = 2
• Alice receives n = 2 (even number)

Alice's turn (n = 2):

• Available divisors of 2 that are less than 2: {1}
• Alice chooses x = 1
• New value: n = 2 - 1 = 1
• Bob receives n = 1

Bob's turn (n = 1):

• No divisors exist where 0 < x < 1
• Bob cannot make a move and loses
• Alice wins!

Notice the pattern: Alice consistently receives even numbers (6, 4, 2) and always chooses to subtract 1, while Bob consistently receives odd numbers (5, 3, 1) and has no choice but to subtract an odd divisor, returning an even number to Alice. This demonstrates why starting with an even number guarantees victory with optimal play.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the solution only performs a single modulo operation (n % 2) and a comparison (== 0), both of which are constant-time operations regardless of the input size n.

The space complexity is O(1) because the solution uses only a fixed amount of memory - no additional data structures are created, and the space usage doesn't scale with the input n. The function simply returns a boolean value based on a direct calculation.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overcomplicating with Dynamic Programming or Recursion

Many developers initially approach this problem by trying to simulate the entire game using dynamic programming or recursion with memoization:

# Overcomplicated approach - unnecessary!
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]

Why it's a pitfall: While this approach works correctly, it has O(n²) time complexity and O(n) space complexity, when the problem can be solved in O(1) time and space.

Solution: Recognize the mathematical pattern through small examples and induction rather than brute-forcing all game states.

2. Misunderstanding the Optimal Play Assumption

Some might think they need to find the "best" divisor choice at each step:

# Wrong assumption - trying to find "best" move
class Solution:
    def divisorGame(self, n: int) -> bool:
        # Trying to choose the largest divisor or specific strategies
        divisors = [x for x in range(1, n) if n % x == 0]
        # Complex logic to choose "optimal" divisor...

Why it's a pitfall: The problem states both players play optimally, which means they'll make any move that leads to their victory. For even numbers, choosing x=1 is always sufficient to maintain the winning position.

Solution: Understand that "optimal play" means making any move that preserves your winning position, not necessarily the "largest" or "smallest" divisor.

3. Not Recognizing the Even/Odd Pattern

Some solutions check specific numbers without recognizing the general pattern:

# Incomplete pattern recognition
class Solution:
    def divisorGame(self, n: int) -> bool:
        if n == 1:
            return False
        if n == 2:
            return True
        if n == 3:
            return False
        # ... continuing with specific cases

Why it's a pitfall: This leads to incomplete solutions that might fail for larger values of n or require extensive case-by-case analysis.

Solution: Test a few small values (n=1,2,3,4,5,6) and observe that Alice wins for all even n and loses for all odd n. Then prove this pattern mathematically.

4. Incorrect Implementation of the Modulo Check

A simple but critical error could be reversing the boolean logic:

# Wrong - reversed logic!
class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 1  # This would mean Alice wins on odd numbers

Why it's a pitfall: This completely inverts the answer, making all test cases fail.

Solution: Verify with simple examples: n=2 should return True (Alice wins), n=3 should return False (Bob wins). The correct condition is n % 2 == 0.