Watch 10 video solutions for Divisor Game, a easy level problem involving Math, Dynamic Programming, Brainteaser. This walkthrough by Fraz has 25,592 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |