Domain 1EasyCORE

Divisor Game

The problem involves two players, Alice and Bob, taking turns playing a game with a number `n` initially on a chalkboard. On each turn, a player must choose any divisor `x` of `n` (where `0 < x < n`) and replace `n` with `n - x`. The player who cannot make a move loses the game. We need to determine if Alice wins given that both players play optimally.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#Dynamic Programming

1025. Divisor Game

Model: qwen2.5-coder:14b
Topics: Math,Dynamic Programming
FAANG asked: 1
Acceptance rate: 66.1%


Problem Breakdown

The problem involves two players, Alice and Bob, taking turns playing a game with a number n initially on a chalkboard. On each turn, a player must choose any divisor x of n (where 0 < x < n) and replace n with n - x. The player who cannot make a move loses the game. We need to determine if Alice wins given that both players play optimally.

Inputs:

  • An integer n representing the initial number on the chalkboard.

Outputs:

  • A boolean value indicating whether Alice wins (true) or loses (false).

Implicit Constraints/Edge Cases:

  • If n = 1, Alice cannot make a move and thus loses.
  • The problem guarantees that 1 <= n <= 1000.

Intuition

A brute-force approach would involve simulating all possible moves for both players, which is computationally expensive due to the exponential number of game states. This approach is insufficient because it has high time complexity.

The key insight is to recognize a pattern in the game outcomes based on whether n is even or odd:

  • If n is even, Alice can always win by choosing x = 1, reducing n to an odd number for Bob. This forces Bob into a losing position because any divisor of an odd number is also odd, and subtracting an odd number from another odd number results in an even number.
  • If n is odd, Alice will always lose because any divisor of an odd number is odd, and subtracting an odd number from another odd number results in an even number. This puts Bob in a winning position.

Approach

Given the insight above, we can determine the winner based solely on whether n is even or odd:

  • If n is even, return true.
  • If n is odd, return false.

This approach leverages mathematical properties to achieve constant time complexity without simulating the entire game.

Complexity Analysis

  • Time Complexity: O(1) because the solution involves a simple conditional check.
  • Space Complexity: O(1) as no additional data structures are used.

Solution

def divisorGame(n: int) -> bool:
    # Alice wins if n is even, loses if n is odd
    return n % 2 == 0

Edge Cases Handled

  • n = 1: The function correctly returns false because Alice cannot make a move.
  • n = 2: The function correctly returns true because Alice can choose x = 1, leaving Bob with no moves.
  • n = 1000 (maximum constraint): The function handles this efficiently within the constraints.