Code Logo

Divisor Game

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Alice and Bob take turns playing a game with a starting number n. On each turn, a player chooses any x such that 0 < x < n and n % x == 0, then replaces n with n - x. Alice moves first. If a player cannot make a move, they lose. Return true if Alice can win the game, assuming both players play optimally.

This game can be solved with DP by computing win/lose states from 1 to n. A position i is winning if there exists a valid move x such that i - x is a losing position. The base case: dp[1] = false because no divisor x exists in (0, 1) that divides 1.

The recurrence is:dp[i] = true if there exists x where i % x == 0 and !dp[i - x]. The time complexity is O(n²) but can be optimized to O(1) with the observation that Alice wins if and only if n is even.

Edge cases include n = 1 (Alice loses, no move possible), n = 2 (Alice picks x = 1, n becomes 1, Bob loses), and large n where the DP approach still runs efficiently.

The divisor game DP demonstrates optimal play in a two-player game. A position is winning if there exists a move to a losing position. The inner loop checks all possible divisors x of i, and if moving to i-x forces a loss for the opponent, the current position is winning.

Example Input & Output

Example 1
Input
3
Output
false
Explanation

Alice picks x=1, n=2; Bob picks x=1, n=1. Bob wins.

Example 2
Input
5
Output
false
Explanation

Odd number, Alice loses.

Example 3
Input
4
Output
true
Explanation

Alice picks x=1, n=3 (Bob loses).

Example 4
Input
2
Output
true
Explanation

Alice picks x=1, n=1. Alice wins.

Example 5
Input
1
Output
false
Explanation

Alice cannot move. Bob wins.

Algorithm Flow

Recommendation Algorithm Flow for Divisor Game

Solution Approach

Alice and Bob play a game where Alice chooses a divisor x of n (1 < x < n), subtracts it from n, and passes the new n to Bob. The player who cannot make a move (n is odd and has no odd divisor) loses. For even n, Alice can always win by subtracting 1, making n odd. For odd n, any divisor is odd, so subtracting an odd from an odd gives an even number for the opponent. Return true if Alice wins with optimal play.

function divisorGame(n) {
  return n % 2 === 0;
}

If n is even, Alice subtracts 1 to make it odd for Bob. Bob then must subtract an odd divisor, making it even again. This cycle continues until n reaches 1, which Bob cannot play because the only divisor is 1 (which is not less than n). Alice wins all even starting numbers.

Time complexity is O(1), space complexity is O(1).

Best Answers

java
class Solution {
    public boolean solution(int n) {
        boolean[] dp = new boolean[n + 1];
        dp[0] = false;
        dp[1] = false;
        for (int i = 2; i <= n; i++) {
            for (int x = 1; x < i; x++) {
                if (i % x == 0 && !dp[i - x]) { dp[i] = true; break; }
            }
        }
        return dp[n];
    }
}