Leetcode 1025. Divisor Game

Problem description

In this game, Alice and Bob take turns selecting a positive divisor of the current number in play, and subtracting that divisor from the current number. If a player cannot make a move (i.e., there are no divisors left besides the number itself), they lose the game. Since Alice plays first, we are asked to determine if Alice can win the game given an initial number.

How the game works

Let's look at a couple of examples to illustrate the game.

If the initial number is 2, Alice starts and can choose 1 (the only available divisor), leaving Bob with the number 1. Bob has no possible moves (since the only divisor of 1 is 1 itself), so Alice wins.

If the initial number is 3, Alice again starts and can choose 1 (again, the only available divisor), leaving Bob with the number 2. Bob can now choose 1, leaving Alice with the number 1 and no possible moves, so Bob wins.

Solution Approach

The solution works on the fact that if the initial number is even, Alice always wins, while if the number is odd, Bob wins. This is because, when the number is even, Alice can always subtract 1 (a divisor of any integer). This will always leave an odd number for Bob. No matter what divisor Bob subtracts (which should be odd since an odd number cannot have an even divisor), an even number will always be left for Alice. By repeating this strategy, Alice always ends up with the number 2 on her turn and will win on the next turn.

Coding part

In all the below codes, we just need to return True if the initial number is even (i.e., n % 2 == 0), and False otherwise.

Python Solution

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

Java Solution

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

Javascript Solution

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

C++ Solution

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

C# Solution

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

All of these codes return the result whether the number is even or not, thus deciding who will win the game.The codes presented above are simple and extremely efficient. They run in O(1) time complexity, which means they run the same regardless of the size of the input. Therefore, this is a perfect solution that we need with regards to efficiency.

Assume that the initial number is N and, Alice uses the best strategy. Alice can always win by one of the two ways:

• If N is even, Alice can choose x = 1 and decrement the number by one to make it odd. And follow the step 2.
• If N is odd, then it must have some odd divisor (For example, 1 is an odd divisor). After the subtraction, the number N' is still even. Eventually, Alice will hit N = 2 from some even N and wins the game.

Therefore, if the initial number (N) is even then Alice will win otherwise Bob will for sure with the best strategy. They simply follow the rules of the game and choose the divisor cleverly.

The problem is a great example of simple mathematics in programming. The solution exploits the properties of even and odd integers and the rules of the game. Don't complicate it with dynamic programming or brute-force approaches, the mathematics behind the problem leads us to a constant solution. This is an important lesson for tackling other competitive programming problems as well, often simpler mathematical solutions can save time and are more efficient.