algoadvance

1025. 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:

1. Choosing any x with 0 < x < N and N % x == 0.
2. 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.

Clarifying Questions

1. Clarification on N:
   • Can N be any positive integer within a specific range?
     • Yes, N is a positive integer, and the constraints generally imply 1 <= N <= 1000.
2. Game Rules:
   • For every move, a player reduces N by some divisor of N less than N itself?
     • Correct.

Strategy

The game exhibits a pattern based on whether N is even or odd.

• If N is even, Alice can force a win by playing optimally.
• If N is odd, Alice cannot force a win if Bob also plays optimally.

Reasoning:

1. If N = 1, Alice loses because she cannot make any valid moves.
2. If N = 2, Alice wins by subtracting 1 (the only valid move).
3. If N = 3, Alice loses because she subtracts 1, making it N = 2 for Bob’s turn, and Bob will win.
4. If N = 4, Alice can subtract 1, leaving N = 3 for Bob’s turn. Bob loses at N = 3, so Alice wins.

From this, we observe that:

• For even N, the opponent always faces an odd N after Alice’s turn.
• For odd N, Alice faces an even N on the opponent’s turn after subtracting an odd divisor less than N.

This pattern holds up through larger values of N.

Code

def divisorGame(N: int) -> bool:
    return N % 2 == 0

Time Complexity

The time complexity of this solution is O(1) (constant time) since it only involves determining whether N is even or odd, which is a single operation. No iterations or recursive calls are required.

Explanation

1. If N is even, N % 2 == 0 returns True, and Alice wins.
2. If N is odd, N % 2 != 0 returns False, and Alice loses.

This optimal strategy is derived from patterns observed through mathematical reasoning and ensures both players are playing optimally.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?