Code Implementation

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

class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};
      

class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}
      

var divisorGame = function(n) {
    return n % 2 === 0;
};
      

Problem Description

The Divisor Game is a two-player game involving a single positive integer n. The game is played as follows:

• On each player's turn, they must choose a number x such that 0 < x < n and n % x == 0 (i.e., x is a positive divisor of n).
• After choosing x, the current player replaces n with n - x.
• The player who cannot make a move (because n == 1) loses the game.

The problem asks: Given the starting integer n, determine if the first player (Alice) can guarantee a win, assuming both players play optimally.

Thought Process

At first glance, this problem seems to require simulating all possible moves and outcomes, which could get complicated quickly. A brute-force approach might involve recursively trying every possible divisor and seeing if the first player can force a win. However, with careful observation, we might find patterns or properties that simplify the problem.

By analyzing small values of n, we can look for a winning strategy. For example, for n = 1, no moves are possible, so the first player loses. For n = 2, the first player can subtract 1 (since 1 is a divisor of 2), leaving 1 for the opponent, who then loses. This pattern continues, and by checking more numbers, we might notice that the outcome depends on whether n is even or odd.

This leads us to consider whether parity (even or odd) of n determines the winner, rather than simulating every move.

Solution Approach

Let's break down the algorithm step-by-step:

1. Base Cases:
   • If n == 1, Alice cannot move and loses.
   • If n == 2, Alice can subtract 1, making n = 1 for Bob, so Alice wins.
2. Pattern Recognition:
   • Try small values of n and see who wins if both play optimally.
   • Notice that Alice wins when n is even and loses when n is odd.
3. Why Does This Work?
   • If n is even, Alice can always subtract 1 (since 1 divides any number), making n odd for Bob.
   • Whenever Bob gets an odd number, any divisor he picks and subtracts will result in an even number for Alice.
   • This continues until n becomes 1, at which point the player with an odd number loses.
4. Conclusion:
   • Alice wins if and only if n is even. The solution is simply to check the parity of n.

This approach avoids recursion or simulation, making it highly efficient.

Example Walkthrough

Let's use n = 4 as an example:

1. Alice starts with n = 4 (even).
2. Alice can pick x = 1 (since 1 divides 4), making n = 3 for Bob.
3. Bob now has n = 3 (odd). His only move is x = 1, making n = 2 for Alice.
4. Alice now has n = 2 (even). She picks x = 1, making n = 1 for Bob.
5. Bob has n = 1 and cannot move. Alice wins.

This pattern holds for any even n: Alice can always force Bob into an odd number, and eventually win.

Time and Space Complexity

Brute-force Approach:

• Would involve recursively checking all possible moves, leading to exponential time complexity: O(2^n) or worse.
• Space complexity would also be high due to the recursion stack.

• Time complexity: O(1) — Only a single modulo operation is performed.
• Space complexity: O(1) — No additional data structures are used.

This makes the solution extremely efficient, regardless of the input size.

Summary

The Divisor Game problem can be elegantly solved by recognizing a simple pattern: the first player (Alice) wins if and only if the starting number n is even. This insight removes the need for complex simulations or recursion. The solution is efficient, requiring only a parity check, and demonstrates the power of pattern recognition and mathematical reasoning in algorithmic problem-solving.