Divisor Game — Editorial

Opening the reading…

Intuitionwhy only the parity of n matters

Start with an odd number. Every divisor of an odd number is odd, so every legal move subtracts an odd value from odd n and leaves an even number. Therefore, from an odd position, every move gives the opponent an even position. The player who receives an even position can respond by subtracting 1, because 1 is a proper divisor of every n greater than 1.

That response creates a pair of moves: odd goes to even, then even goes to odd. The player facing an odd number cannot escape this pattern, while the player facing an even number can force it by subtracting 1. Since 1 has no legal move, it is losing, so every even starting number is winning and every odd starting number is losing.

Approach

Treat n as a position rather than trying to count all possible games, because optimal play depends only on whether the current number is even or odd.

Observe that every divisor of an odd n is odd, so any move from odd n produces an even number; without this fact, the losing-position argument has no foundation.

Observe that every even n greater than 1 allows the move x = 1, which produces n - 1, an odd number; this gives the player at an even position a guaranteed move to the losing kind of position.

Use 1 as the base case: it is odd and has no proper positive divisor, so the player whose turn it is loses immediately.

Return whether n is even, because even positions can move to odd positions and odd positions can only move to even positions.

Complexitythe result requires no search

MEASURE	BOUND	WHY
Time	O(1)	The solution performs one remainder operation and one boolean return. It does not enumerate divisors or game states, so the work does not grow with n.
Space	O(1)	Only the input value and a constant amount of temporary state are used. The returned boolean is required output and is excluded from the extra-space bound; the bound stays O(1) for every possible input value.

Here n is the starting number on the chalkboard.

Annotated solutionC++ · parity check · the complete judge-ready implementation

CPPReturn true exactly when the starting number is even.

#include <iostream>

using namespace std;

class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};

The entire proof is concentrated in the return condition. For even n, subtracting 1 reaches an odd position, and every move from an odd position reaches an even one. The code does not need to find the divisor or simulate the opponent, because the existence of the winning response is enough to classify the starting position.