Code Logo

Divisor Game

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Divisor Game

Solution Approach

DP array for n+1. For each i, check all divisors x. If any leads to losing position, i is winning.

function solution(n) {
  var dp = new Array(n + 1);
  dp[0] = false;
  dp[1] = false;
  for (var i = 2; i <= n; i++) {
    dp[i] = false;
    for (var x = 1; x < i; x++) {
      if (i % x === 0 && !dp[i - x]) { dp[i] = true; break; }
    }
  }
  return dp[n];
}

Time O(n²), Space O(n).

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];
    }
}