Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Divisor Game solution and explanation

EasyBrainteaserDynamic ProgrammingGame TheoryMath5 min read72.3% acceptanceUpdated 9 Apr 2026
Asked atVisaGoogleMetaTCSAmazonMicrosoft
+1 moreBloomberg
Practise Divisor Game
17:30
Leetcode 1025. Divisor GameFraz · 17:30 · 25K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode 1025. Divisor GameFraz · 17:30 · 25K views
  2. Dynamic programming (1025. Divisor Game - Leetcode )Ajay Prakash · 20:19 · 8K views
  3. Divisor Game 🚀 Leetcode 1025 Recursion Code | DP Complete Playlist in HindiHello World · 16:46 · 8K views
  4. Divisor Game | LEETCODE - 1025 | Easy solutionhi-malik · 10:07 · 5K views
  5. 1025. Divisor Game | LEETCODE EASY | DYNAMIC PROGRAMMINGcode Explainer · 10:44 · 3K views
  6. 1025. DIVISOR GAME Leetcode problem/ Explanation + C++ codeCoding with U · 4:18 · 2K views
  7. Divisor Game | Leetcode #1025 | Dynamic Programming | Data Structures and AlgorithmMukul Bansal · 18:54 · 1K views
  8. 1025. (Easy) Divisor Game - Daily Leetcode (Day 82)yeetcode · 2:44 · 1K views
  9. 2. Divisor Game | Leetcode - 1025 | Dynamic ProgrammingAceCoder Academy · 22:49 · 839 views
  10. 1025. Divisor Game with pythonn | Best Explanation | Leetcode with PythonArsalan Ahmed · 4:06 · 584 views

The problem

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

  • Choosing any x with 0 < x < n and n % x == 0.
  • Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Constraints:

  • 1 <= n <= 1000

Approach overview

Problem Overview: You start with an integer n. Two players take turns choosing a divisor x such that 0 < x < n and n % x == 0, then replace n with n - x. The player who cannot make a move loses. The task is to determine whether Alice (the first player) wins assuming both players play optimally.

Approach 1: Dynamic Programming (Time: O(n²), Space: O(n))

This approach models the game as a classic state transition problem from dynamic programming. Let dp[i] represent whether the current player can win with number i. For each i, iterate through all possible divisors x where i % x == 0 and x < i. If any move leads to a losing state for the opponent (dp[i - x] == false), then dp[i] becomes true. This works because optimal play always forces the opponent into a losing configuration whenever possible. The algorithm builds results from 1 up to n, checking all valid moves. Although straightforward and easy to reason about, the nested iteration over numbers and divisors leads to O(n²) time in the worst case.

Approach 2: Mathematical Observation (Even/Odd Strategy) (Time: O(1), Space: O(1))

The key insight comes from analyzing patterns in the game using math and game theory. If n is even, Alice can always subtract 1, leaving an odd number for Bob. From any odd number, every divisor is also odd, so the result of n - x becomes even again. This forces Bob to always hand back an even number. Eventually Bob receives 1, which has no valid moves. If n starts odd, Alice can only subtract an odd divisor, turning the value even and giving the advantage to Bob. The pattern holds for all values: even numbers are winning states, odd numbers are losing states. The final solution reduces to a simple check: Alice wins if n % 2 == 0.

Recommended for interviews: Start with the dynamic programming formulation because it demonstrates that you understand state transitions and optimal play in game problems. After observing the pattern for small values, derive the mathematical rule that all even numbers are winning states. Interviewers usually expect the O(1) parity observation as the final answer because it shows deeper reasoning beyond brute-force simulation.

Approach 1: Approach 1: Mathematical Observation (Even/Odd Strategy)

The game can be reduced to noticing the pattern of winning or losing based on whether n is even or odd. If n is even, Alice can make the number odd by removing 1. Bob will always receive an odd number to play with, ensuring Alice's win if both play optimally.

def divisorGame(n: int) -> bool:
    return n % 2 == 0
class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}
class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};
var divisorGame = function(n) {
    return n % 2 === 0;
};
#include <stdbool.h>
bool divisorGame(int n) {
    return n % 2 == 0;
}
public class Solution {
    public bool DivisorGame(int n) {
        return n % 2 == 0;
    }
}

Python code utilizes the same simple check for an even number to determine Alice's win condition.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Approach 2: Dynamic Programming

We can use dynamic programming to determine the winning and losing states for each value of n. By understanding which states lead to a win, we can implement a solution that explores the outcomes based on possible moves.

def divisorGame(n: int) -> bool:
    dp = [False] * (n + 1)
    for i in range(2, n + 1):
        for x in range(1, i):
            if i % x == 0 and not dp[i - x]:
                dp[i] = True
                break
    return dp[n]
class Solution {
    public boolean divisorGame(int n) {
        boolean[] dp = new boolean[n + 1];
        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];
    }
}
#include <vector>
using namespace std;

class Solution {
public:
    bool divisorGame(int n) {
        vector<bool> dp(n + 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];
    }
};
var divisorGame = function(n) {
    const dp = Array(n + 1).fill(false);
    for (let i = 2; i <= n; i++) {
        for (let x = 1; x < i; x++) {
            if (i % x === 0 && !dp[i - x]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
};
#include <stdbool.h>

bool divisorGame(int n) {
    bool dp[n + 1];
    dp[1] = false;
    for (int i = 2; i <= n; i++) {
        dp[i] = false;
        for (int x = 1; x < i; x++) {
            if (i % x == 0 && !dp[i - x]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}
public class Solution {
    public bool DivisorGame(int n) {
        bool[] dp = new bool[n + 1];
        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];
    }
}

In Python, we use a list dp to track the win-lose status of each state. The nested loops consider all moves for each quantity on the board.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Try this approach in the editor

Approach 3: Mathematical Induction

  • When n=1, the first player loses.
  • When n=2, the first player takes 1, leaving 1, the second player loses, the first player wins.
  • When n=3, the first player takes 1, leaving 2, the second player wins, the first player loses.
  • When n=4, the first player takes 1, leaving 3, the second player loses, the first player wins.
  • ...

We conjecture that when n is odd, the first player loses; when n is even, the first player wins.

Proof:

  1. If n=1 or n=2, the conclusion holds.
  2. If n \gt 2, assume that the conclusion holds when n \le k, then when n=k+1:
    • If k+1 is odd, since x is a divisor of k+1, then x can only be odd, so k+1-x is even, the second player wins, the first player loses.
    • If k+1 is even, now x can be either odd 1 or even. If x is odd, then k+1-x is odd, the second player loses, the first player wins.

In conclusion, when n is odd, the first player loses; when n is even, the first player wins. The conclusion is correct.

The time complexity is O(1), and the space complexity is O(1).

func divisorGame(n int) bool {
	return n%2 == 0
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Mathematical Observation (Even/Odd Strategy)

Time Complexity: O(1)
Space Complexity: O(1)

Approach 2: Dynamic Programming

Time Complexity: O(n^2)
Space Complexity: O(n)

Mathematical Induction–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(n²)O(n)When learning the game-state transition or deriving the pattern step-by-step
Mathematical Observation (Even/Odd Strategy)O(1)O(1)Optimal solution for interviews and production; relies on parity insight

Frequently asked questions

Is Divisor Game easy or hard?

Divisor Game is classified as an Easy problem on LeetCode with an acceptance rate above 70%. The challenge is recognizing the parity pattern behind the moves rather than implementing complex logic.

Divisor Game Python/Java solution

In Python or Java, the optimal implementation is a single line that returns whether n is even. For example: return n % 2 == 0. This leverages the mathematical insight that every even number is a winning state for the first player.

How to solve Divisor Game in O(n)?

Most straightforward implementations use dynamic programming with O(n²) time, checking all divisors for each value. However, observing the parity pattern reveals that all even numbers are winning states and all odd numbers are losing states. That reduces the solution to O(1) time by returning n % 2 == 0.

What is the best approach for Divisor Game?

The best approach is the mathematical observation that Alice wins if and only if n is even. This works because subtracting 1 from an even number forces the opponent into an odd number, and every move from an odd number returns an even number. The solution runs in O(1) time and O(1) space.

Is Divisor Game asked at Google/Amazon/Meta?

Divisor Game represents a common class of interview problems involving game theory and mathematical patterns. Variations of turn-based divisor or subtraction games appear in interviews at large tech companies because they test reasoning about optimal play and state transitions.

What data structure is used in Divisor Game?

The dynamic programming solution uses a simple boolean array dp[] where dp[i] represents whether the current player can win with value i. The optimal mathematical solution does not require any data structure and only performs a parity check.

What is the time complexity of Divisor Game?

The optimal mathematical solution runs in O(1) time and O(1) space because it only checks whether n is even. A dynamic programming approach that evaluates all states from 1 to n takes O(n²) time and O(n) space.

Comments

Now write it yourselfClose this page and solve Divisor Game in the editor, without looking.
Practise Divisor Game