Divisor Game
Easy · Dynamic Programming · Math · Dynamic Programming · Game Theory
Problem
Alice and Bob play a game with a single number n written on a board. Alice moves first, and they alternate turns.
On a turn the current player picks an integer x with 0 < x < n that divides n exactly (n % x == 0), then replaces n with n - x. A player who has no legal move loses.
Assuming both play perfectly, return true if Alice wins and false otherwise.
Examples
Input: n = 4 Output: true
Alice subtracts 1 to leave 3; Bob must subtract 1 to leave 2; Alice subtracts 1 to leave 1 and Bob is stuck.
Input: n = 7 Output: false
The only divisor of 7 below 7 is 1, so Alice leaves 6, an even number, and Bob keeps Alice on odd numbers from then on.
Input: n = 1 Output: false
There is no x with 0 < x < 1, so Alice cannot move and loses at once.
Constraints
- 1 <= n <= 1000
Approaches
- Baseline: win/lose table over all numbers — time O(n²), space O(n)
Follow-up
The table from the baseline is the general tool for two-player games with perfect play; the parity rule is what this particular move set allows. The use cases change the moves: taking 1 to 3 stones gives another simple rule (multiples of 4 lose), while taking a perfect square gives none, so the table is the solution.
Related problems
Start free on Cariara · Coding problems · System design studio
