1025. Divisor Game #

Problem #

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:

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

Example 1:

Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1 <= N <= 1000

Problem Summary #

Alice and Bob play a game together, taking turns. Alice starts first. Initially, there is a number N on the chalkboard. On each player’s turn, the player needs to perform the following operations:

Choose any x, satisfying 0 < x < N and N % x == 0 .
Replace the number N on the chalkboard with N - x .

If a player cannot perform these operations, they lose the game. Return True only when Alice wins the game; otherwise return false. Assume both players participate in the game optimally.

Solution Ideas #

Two people play a game against each other. Initially, there is a number N. When the game starts, either side chooses a number x satisfying the conditions 0 < x < N and N % x == 0, and then N-x becomes the number for the start of the next round. This round ends, and the other person continues choosing a number; the two take turns choosing. When one side can no longer choose a number, that side loses the game. The question is, if you start first, given N, can you know whether you will definitely win or definitely lose this game?
In this problem, when N = 1, the person whose turn it is must lose. This is because there is no number that can satisfy the conditions 0 < x < N and N % x == 0. The winning strategy is to force the opponent into the situation where N = 1. The problem assumes that the opponent is also very smart. If initially N is even, I choose x = 1, and the number the opponent gets is odd. As long as I can eventually make the opponent get an odd number, they will lose. If initially N is odd, when N = 1 we lose directly; when N is another odd number, we can only choose an odd x (because N % x == 0, N is odd, and x definitely cannot be even, because an even number would be divisible by 2). Since the opponent is very smart, when after our choice N - x is even, they will choose 1, so the number we get on our turn is odd again. As long as the opponent keeps ensuring that we get an odd number, they will eventually force us to get 1, and they will ultimately win. Therefore, after analysis, if the initial number is even, there is a winning strategy; if the initial number is odd, there is a losing strategy.

Code #


package leetcode

func divisorGame(N int) bool {
	return N%2 == 0
}