Problem Description
Alice and Bob play a game starting with a number n on a chalkboard. On each turn, the current player chooses any x such that 0 < x < n and n % x == 0, then replaces n with n - x. The player unable to make a move loses. Return true if and only if Alice wins the game given both players play optimally.
Key Insights
- When n is even, Alice can always force an odd number on Bob by choosing x=1.
- When n is odd, any valid move will result in an even number, favoring the opponent.
- Thus, the result depends solely on whether n is even.
Space and Time Complexity
Time Complexity: O(1) Space Complexity: O(1)
Solution
The solution leverages the observation that Alice wins if and only if n is even. If n is even, she can always subtract 1 (a valid divisor) and force n to be odd for Bob’s turn. For any odd n, every valid divisor is odd, meaning the next turn always produces an even number for the opponent. Therefore, the winning condition for Alice is simply checking if n is even.