Divisor Game

Divisor Game

What is this problem about?

The Divisor Game interview question is a strategic game played between two players, Alice and Bob, starting with a number n. Alice goes first. On each player's turn, they must choose a number x such that 0 < x < n and n % x == 0. They then replace n with n - x. A player loses if they cannot make a move. The goal is to determine if Alice will win the game, assuming both players play optimally.

Why is this asked in interviews?

This problem is a classic example of game theory interview pattern. It's asked by companies like Microsoft and Amazon because it tests a candidate's ability to recognize patterns and perform mathematical induction. While it can be solved using dynamic programming, the optimal solution is a simple parity check, which reveals whether a candidate can think critically about game states and transitions.

Algorithmic pattern used

This problem involves Math and Brainteasers. By analyzing small values of n, you can observe a pattern:

• If n is even, Alice can always choose x = 1, making n - 1 odd for Bob.
• If Bob gets an odd n, any divisor x must also be odd (since odd numbers only have odd divisors). This makes n - x even for Alice.
• Alice can continue this strategy until Bob gets n = 1 and cannot move. Thus, Alice wins if n % 2 == 0.

Example explanation

Let's look at n = 3.

1. Alice must choose x such that 3 % x == 0 and 0 < x < 3. The only choice is x = 1.
2. Alice replaces 3 with 3 - 1 = 2.
3. Now it's Bob's turn with n = 2. Bob chooses x = 1.
4. Bob replaces 2 with 2 - 1 = 1.
5. Now it's Alice's turn with n = 1. She cannot make a move.
6. Alice loses. Now look at n = 2. Alice chooses x = 1, Bob gets n = 1 and loses. Alice wins.

Common mistakes candidates make

• Over-engineering with DP: Building a full dynamic programming table when a simple parity check is sufficient. While DP works, it takes more time and space.
• Ignoring Optimal Play: Not realizing that "optimal play" means Alice will always try to force Bob into a losing state.
• Miscalculating Divisors: Forgetting that x must be strictly less than n.

Interview preparation tip

For game theory problems, always start by manually tracing the first 5-10 states. Patterns (like parity or cycles) often emerge that simplify the problem significantly.