Skip to main content
Talentd

Divisor Game - Solution & Explanation

EasyMathDynamic ProgrammingBrainteaserGame Theory14 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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.

The solution is straightforward. If n is even, Alice returns true, meaning she wins. If n is odd, she returns false, as Bob wins. Only one line of logic is involved in making this decision: return n % 2 == 0;.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) because it's a constant-time operation.
Space Complexity: O(1) because it uses no extra space aside from input.

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.

This C solution defines a dynamic programming array where dp[i] is true if Alice can force a win from the state where n = i. We iterate through all possible x values for each i to check if there is a move that leaves Bob in a losing position.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) because of the nested loop over n and possible moves x.
Space Complexity: O(n) for storing the results of all states.

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).

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

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

Time Complexity: O(1) because it's a constant-time operation.
Space Complexity: O(1) because it uses no extra space aside from input.

Approach 2: Dynamic Programming

Time Complexity: O(n^2) because of the nested loop over n and possible moves x.
Space Complexity: O(n) for storing the results of all states.

Mathematical Induction—

Detailed 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

Video Solution

Leetcode 1025. Divisor Game • Fraz • 25,769 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Divisor Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer