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
nrepresenting 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
nis even, Alice can always win by choosingx = 1, reducingnto 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
nis 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
nis even, returntrue. - If
nis odd, returnfalse.
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
falsebecause Alice cannot make a move. - n = 2: The function correctly returns
truebecause Alice can choosex = 1, leaving Bob with no moves. - n = 1000 (maximum constraint): The function handles this efficiently within the constraints.