Determine the Winner of Repeated Proper-Divisor Subtraction
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Two players alternate from positive integer n, with the first player moving first. A legal move chooses a positive proper divisor x of the current number and replaces that number by n-x. A player with no legal move loses. Return whether the first player wins with optimal play.
```cpp
class Solution {
public:
bool divisorGame(int n);
};
```
### Examples
**Example 1:**
```text
Input: n = 4
Output: true
Explanation: Subtract1 to leave3. Its only move leaves2, after which subtract1 leaves the opponent at1 without a move.
```
**Example 2:**
```text
Input: n = 5
Output: false
Explanation: Its only proper divisor is1, so the first player must leave4, a winning state for the opponent.
```
### Constraints
- `1 <= n <= 1000`.
### Contract considerations
The game is evaluated under optimal play by both players; it is not a simulation of one arbitrary move sequence.
```hint Read the boundary condition
Every divisor of an odd integer is odd; compare what moves do to parity.
```
### Boundary reminders
The game is evaluated under optimal play by both players; it is not a simulation of one arbitrary move sequence.
Overview: Determine the Winner of Repeated Proper-Divisor Subtraction. Two players alternate from positive integer n, with the first player moving first.
