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:
x with 0 < x < n and n % x == 0.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 <= 1000Problem 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.
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;.
Time Complexity: O(1) because it's a constant-time operation.
Space Complexity: O(1) because it uses no extra space aside from input.
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.
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.
n=1, the first player loses.n=2, the first player takes 1, leaving 1, the second player loses, the first player wins.n=3, the first player takes 1, leaving 2, the second player wins, the first player loses.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:
n=1 or n=2, the conclusion holds.n \gt 2, assume that the conclusion holds when n \le k, then when n=k+1: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.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).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Mathematical Observation (Even/Odd Strategy) | Time Complexity: O(1) because it's a constant-time operation. |
| Approach 2: Dynamic Programming | Time Complexity: O(n^2) because of the nested loop over n and possible moves x. |
| Mathematical Induction | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(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 |
Leetcode 1025. Divisor Game • Fraz • 25,592 views views
Watch 9 more video solutions →Practice Divisor Game with our built-in code editor and test cases.
Practice on FleetCode