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 <= 1000The Divisor Game is a two-player game where players alternately choose a divisor x of the current number n such that 0 < x < n and replace n with n - x. The challenge is to determine whether the first player can guarantee a win assuming both players play optimally.
A common way to reason about this problem is through game state transitions. If there exists a move that forces the opponent into a losing state, the current state is winning. A dynamic programming approach can track whether each number from 1 to n is a winning or losing position by testing all valid divisors.
While DP helps build intuition about winning states, further observation of the pattern reveals a mathematical insight related to the parity of the number. Recognizing this pattern allows the solution to be simplified dramatically, reducing the time and space requirements compared to the DP simulation.
The DP approach helps understand the game mechanics, while the mathematical observation leads to an optimal constant-time solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (checking all divisors) | O(n^2) | O(n) |
| Mathematical Observation | O(1) | O(1) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
If the current number is even, we can always subtract a 1 to make it odd. If the current number is odd, we must subtract an odd number to make it even.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Divisor Game is a common interview question used to test logical reasoning and pattern recognition. Interviewers often expect candidates to start with a DP approach and then identify the mathematical pattern that simplifies the solution.
The optimal approach relies on a mathematical observation derived from analyzing game states. Instead of simulating every move, you can recognize a pattern in winning and losing numbers. This leads to a constant-time decision based on the value of n.
Yes, the problem can be solved using dynamic programming by marking each number as a winning or losing state. For every value, you check all valid divisors and see if moving to a losing state for the opponent is possible. This helps build intuition but is less efficient than the final mathematical insight.
The DP solution typically uses a simple boolean array where each index represents whether the current number is a winning state. The array is filled iteratively from smaller numbers to larger ones based on possible divisor moves.