Divisor Game
Problem
Alice and Bob take turns, with Alice going first. They share a number n on a chalkboard. On a turn the current player picks a divisor x with 0 < x < n and n % x == 0, then replaces n with n − x. A player who cannot move (when n == 1) loses. Assuming both play optimally, return true if Alice wins.
n = 4truedef divisor_game(n):
win = [False] * (n + 1)
for cur in range(2, n + 1):
for x in range(1, cur):
if cur % x == 0 and not win[cur - x]:
win[cur] = True
break
return win[n]function divisorGame(n) {
const win = new Array(n + 1).fill(false);
for (let cur = 2; cur <= n; cur++) {
for (let x = 1; x < cur; x++) {
if (cur % x === 0 && !win[cur - x]) {
win[cur] = true;
break;
}
}
}
return win[n];
}class Solution {
public boolean divisorGame(int n) {
boolean[] win = new boolean[n + 1];
for (int cur = 2; cur <= n; cur++) {
for (int x = 1; x < cur; x++) {
if (cur % x == 0 && !win[cur - x]) {
win[cur] = true;
break;
}
}
}
return win[n];
}
}bool divisorGame(int n) {
vector<bool> win(n + 1, false);
for (int cur = 2; cur <= n; cur++) {
for (int x = 1; x < cur; x++) {
if (cur % x == 0 && !win[cur - x]) {
win[cur] = true;
break;
}
}
}
return win[n];
}Explanation
This is a two-player game, so we reason about who wins from each value using game-theory DP. We define win[v] = true if the player whose turn it is at number v can force a win with perfect play.
A position is winning if there exists any move that hands the opponent a losing position. So for each v, we try every divisor x (with 0 < x < v and v % x == 0); the move sends the opponent to v - x. If win[v - x] is false (opponent loses there), then win[v] is true and we stop.
The base case is win[1] = false: at 1 there is no legal move, so the player to move loses. We fill win[] bottom-up from 2 to n, and the answer is win[n] (Alice moves first).
Example: n = 4. Alice can subtract 1 to leave 3; from 3 Bob's only move leaves 2, then Alice leaves 1 and Bob is stuck. So win[4] is true and Alice wins. (In fact every even n is a win for Alice.)
The DP tries each divisor for each value, so it is quadratic; the famous parity shortcut "even ⇒ Alice wins" gives the same answer in constant time.