Intuition on Leetcode’s Problem 1025 : Divisor Game

The Problem Statement: https://leetcode.com/problems/divisor-game/

Introduction

I will try to lay out my intuition on why this problem can trivially be solved by asking if the input is even or odd.

Definition of Odd Number

The definition for odd number is 2N+1 and the definition of an even number is 2N for any integer N.
So the divisor of any odd number K must only be odd as well. In other word, any integer X that satisfy K % X== 0 must be odd if K is odd.

Choices of Numbers

Depending on the type of integer that you choose, what number will you generate for your opponent?

Firstly, what kind of numbers can you choose?

If you have an even number, you have the choice of both odd and even numbers. At minimum, you can always choose the number 1 (odd) or 2 (even).

On the other hand, if you have an odd number, then you can only choose an odd number. This has to do with the prime divisors of any odd number. Take a number K, and its prime divisors D1,D2,D3, … If any of these are divisible by 2 (definition of an even number), then K must be divisible by 2. Hence, K cannot be an even number.

Now, lets talk about the kind of numbers you generate based on the current number that you have.

Subtracting an odd number from an even number yields an odd number. Simply, 2A+1–2B=2(A-B)+1 for any A and B.

Meanwhile, if you subtract an odd number from an odd number, you get an even number. Simply, 2A+1-(2B+1)=2(A-B) for any integer A and B.

However, as before, if we have an odd number, we can only pick another odd number. Thus, if you have an odd number, you can only generate an even number for your opponent.

You Have Prime Number, You Lose … Except 2

The definition of a prime number is the number must only be divisible by itself and the number 1. Hence, if you have been handed a prime number G, then you can only generate the integer G-1 or 0.

As a note, all prime numbers are odd numbers (except the integer 2) because if they aren’t they are divisible by 2.

The Strategy

If you have been handed an even number, the trick is to always give the other player an odd number.
You do this by always choosing the number 1 to subtract from.
For example, if you are handed the integer 70, then pick integer 1 and the other player will receive the integer 69.

Here, any number the other player choose will get you an even number back. See {Choices of Numbers}.

Now, assuming you follow this trick, the only player who will always be handed the odd numbers is your opponent. Therefore, they are guaranteed to eventually lose.

Namely, they will either:
1. Meet a prime number, OR
2. Meet the number 1, which by definition is a prime number.

You, on the other hand, are always handed an even number and will never lose the game. Unless, of course, you have been handed an odd number at the beginning of the game.

Conclusion

The reason can be illustrated like this:

Even -> Odd -> Even -> Odd -> Even -> Odd -> Even -> Odd -> Even -> Odd -> Even -> Odd -> ….

Notice that when you hand the person an odd number, they have no choice but to give you an even number again.
They will eventually get the number 1 or some other prime number.