Divisor Game#

Alice and Bob are playing a game together, taking turns to make a move, with Alice starting first.
Initially, there is a number N on the blackboard. On each player's turn, the player needs to perform the following operation:

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

If a player cannot perform these operations, they lose the game.
Return true only if Alice wins in the game, otherwise return false, assuming that both players participate in the game in the best state.

Example#

Solution#

/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function(n) {
    return n & 1 ? false : true;
};

Idea#

Understanding the meaning of the question, and based on input and output examples, I infer that this is a game whose outcome is determined by the parity.
Here I quote the official reasoning: When we don't have a solution, let's try writing down a few cases:

• When N = 1, there is no integer in the interval (0, 1) that is a factor of N, so Alice loses.
• When N = 2, Alice can only choose 1, N becomes 1, and Bob cannot continue, so Alice wins.
• When N = 3, Alice can only choose 1, N becomes 2, according to the conclusion of N = 2, we know that Bob will win, and Alice loses.
• When N = 4, Alice can choose 1 or 2, if Alice chooses 1, according to the conclusion of N = 3, Bob will lose, and Alice will win.
• When N = 5, Alice can only choose 1, according to the conclusion of N = 4, Alice will lose.
• ......

By writing down the cases, maybe you have some guesses. It's okay, make bold guesses, because making bold guesses in this situation is the first step towards the correct answer. You may find that for odd N, Alice (the first mover) is always doomed to lose, and for even N, Alice is sure to win. Is this guess correct? Let's try to prove it. Proof: The conclusion holds true for N = 1 and N = 2. For N > 2, assuming that the conclusion holds true for N ≤ k, then for N = k + 1, if k is even, then k + 1 is odd. x is a factor of k + 1, and can only be odd. Subtracting an odd number from an odd number results in an even number, and k + 1 - x ≤ k, so when it's Bob's turn, it's always an even number. And according to our assumption, if N ≤ k is even, then the first mover must win, so no matter what Alice takes away, Bob will be in a winning position, so Alice is in a losing position. If k is odd, then k + 1 is even, and x can be odd or even. If Alice subtracts an odd number, then k + 1 - x is an odd number less than or equal to k. At this point, Bob occupies it and is in a losing position, so Alice is in a winning position. In summary, this guess is correct.

Daily Question#

Reference#