Skip to content

1025. Divisor Game

Description

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 integer 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

Solutions

Solution 1: Mathematical Induction

Thinking

With \(n\le 1000\) we could DP each remaining value: the starter wins if some \(x\) leaves a losing position. Small cases already suggest that odd \(n\) loses and even \(n\) wins, which induction confirms.

A proper divisor of an odd integer is odd, so the opponent receives an even number. From an even integer we can subtract \(1\) and leave an odd number. The outcome depends only on the parity of \(n\).

It is enough to return whether \(n\) is even.

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

1
2
3
class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0

1
2
3
4
5
class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};

1
2
3
func divisorGame(n int) bool {
    return n%2 == 0
}

1
2
3
var divisorGame = function (n) {
    return n % 2 === 0;
};

Comments