Divisor Game

Problem Description

Alice and Bob take turns playing a game with a number n on a chalkboard. Alice starts first. Each player, on their turn, chooses an integer x such that 0 < x < n and n % x == 0, then replaces n with n - x. A player loses if they cannot make a move. The task is to determine if Alice wins the game, assuming both players play optimally.

Key Insights

• The game revolves around making optimal choices based on the current value of n.
• If n is even, Alice can always choose 1, leaving an odd number for Bob, which is a disadvantage.
• If n is odd, no matter what Alice chooses, she will always leave an even number for Bob, giving him a strategic advantage.
• The game's outcome can be determined by the parity (odd or even nature) of n.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The solution to the problem leverages the concept of parity. If n is even, Alice can always win by leaving Bob with an odd number. Conversely, if n is odd, Bob will always win by leaving Alice with an even number. Hence, the solution is straightforward: check the parity of n to determine the winner.

Code Solutions