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:

  • 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.

  • Input: 2

  • Output: true

  • Explanation: Alice chooses 1, and Bob has no more moves.

This problem may seem confusing first, but you can break the question down to some definite cases and work from ther:

  1. Anyone who gets 1 loses, because there is not an x in the range of (0, 1)

  2. Anyone who gets 2 definitely wins, because they can simply take 1 and give 1 back to the opponent, who loses as per point 1.

  3. For any N >= 2, N will be reduced to 2.

This is because:

  1. If N is odd, no matter what X is, X must be odd, then N - X must be even.

  2. For even N, we can always choose x as 1, then N - x = N - 1 must be odd.

Which brings us to the conclusion:

  • Whoever gets an even number N has the choice to get all of the even numbers, including 2, since 2 is even, thus giving them the win.

So if N is even initially:

  1. What will Alice do to win? Choose X = 1, and send odd back to Bob

  2. What will Bob do to win? It does not matter, since he will for sure lose anyway.

So, we know that if Alice gets an even N, she wins the game. So all she has to check for is if N is even.

return (N % 2) == 0;