Divisor Game
James and Oliver are playing a fun number game. The game's strategy is based on recognizing "winning" and "losing" positions for each player. A winning position is one where a player can force a win regardless of what the opponent does, while a losing position is one where the opponent can force a win. Here's how they play:
- They begin with a number,
N, written on the board. - During their turn, with James starting first, a player chooses a number
xsmaller thanNthat dividesNevenly. They then subtractxfromN. - If a player can't find such a number, they lose.
Given the starting number N, assuming both players play optimally, return true if James wins and false if Oliver wins.
Examples:
Example 1:
Starting number: 2
James can pick 1 because that's the only valid choice. Oliver is left with the number 1 and has no valid moves, so James wins.
Why didn't James pick another number? There were no other divisors of 2 less than 2.
Example 2:
Starting number: 3
James chooses 1, making the board show 2. Oliver then has to pick 1 as it's the only option, leaving the number 1 for James who then has no valid moves.
Why didn't James pick another number? There were no other divisors of 3 less than 3.
Example 3:
Starting number: 4
James picks 1, making the board show 3, which is a known losing position (from the previous example). Oliver has no better choice than to pick 1, leading eventually to his loss.
Why didn't James pick 2? If James picked 2, the board would show 2. Oliver would then pick 1, and James would be left with a 1, causing him to lose.
Example 4:
Starting number: 5
James chooses 1, turning the number into a 4 (a winning position as seen earlier). Oliver, even playing optimally, is then set on a path to lose.
Why didn't James pick another number? There were no other divisors of 5 less than 5.