{x}
blog image

Divisor Game

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

  • Choosing any x with 0 < x < n and n % x == 0.
  • Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

 

Example 1:

Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

 

Constraints:

  • 1 <= n <= 1000

Solution Explanation for LeetCode 1025: Divisor Game

This problem can be solved efficiently using mathematical reasoning rather than brute-force game simulation. The core idea is to observe a pattern in the winning and losing conditions based on the value of n.

Mathematical Induction

The solution leverages mathematical induction to prove that the game's outcome depends solely on whether n is even or odd.

  • Base Cases:

    • If n = 1, the first player (Alice) loses because there are no valid moves (0 < x < 1 is impossible).
    • If n = 2, Alice wins by choosing x = 1, leaving Bob with n = 1 and no valid moves.

  • Inductive Hypothesis: Assume that for all k < n, if k is even, the first player wins, and if k is odd, the first player loses.

  • Inductive Step: We need to show that this holds true for n.

    • If n is odd: Any move Alice makes (choosing x such that 0 < x < n and n % x == 0) will result in n - x, which is an even number. By the inductive hypothesis, Bob (the second player) will then win. Therefore, Alice loses when n is odd.
    • If n is even: Alice can always choose x = 1. This leaves Bob with an odd number n - 1, and by the inductive hypothesis, Bob will lose. Therefore, Alice wins when n is even.

This proves that Alice wins if and only if n is even.

Time and Space Complexity

The solution's time complexity is O(1) because it involves a single modulo operation (n % 2). The space complexity is also O(1) as it uses constant extra space.

Code Implementation

The code implementations across different languages are remarkably simple because of the direct relationship between the parity of n and the game's outcome.

Python:

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

Java:

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

C++:

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

Go:

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

JavaScript:

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

All these implementations directly return true if n is even and false otherwise, reflecting the mathematical proof. They are highly optimized for speed and memory efficiency.