LeetCode 1025 - Divisor Game

https://leetcode.com/problems/divisor-game/

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 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: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1. 1 <= N <= 1000

https://leetcode.com/problems/divisor-game/discuss/274606/JavaC%2B%2BPython-return-N-2-0

If N is even, can win.
If N is odd, will lose.

Recursive Prove （Top-down)

1. If N is even.
   We can choose x = 1.
   The opponent will get N - 1, which is a odd.
   Reduce to the case odd and he will lose.
2. If N is odd,
   2.1 If N = 1, lose directly.
   2.2 We have to choose an odd x.
   The opponent will get N - x, which is a even.
   Reduce to the case even and he will win.
3. So the N will change odd and even alternatively until N = 1.

Mathematical Induction Prove （Bottom-up)

1. N = 1, lose directly
2. N = 2, will win choosing x = 1.
3. N = 3, must lose choosing x = 1.
4. N = 4, will win choosing x = 1.

....

For N <= n, we have find that:
If N is even, can win.
If N is odd, will lose.

For the case N = n + 1
If N is even, we can win choosing x = 1,
give the opponent an odd number N - 1 = n,
force him to lose,
because we have found that all odd N <= n will lose.

If N is odd, there is no even x that N % x == 0.
As a result, we give the opponent a even number N - x,
and the opponent can win,
because we have found that all even N <= n can win.

Now we prove that, for all N <= n,
If N is even, can win.
If N is odd, will lose.

Java/C++:

        return N % 2 == 0;

https://leetcode.com/problems/divisor-game/discuss/274566/just-return-N-2-0-(proof)

prove it by two steps:

1. if Alice will lose for N, then Alice will must win for N+1, since Alice can first just make N decrease 1.
2. for any odd number N, it only has odd factor, so after the first move, it will be an even number

let's check the inference
fisrt N = 1, Alice lose. then Alice will must win for 2.
if N = 3, since all even number(2) smaller than 3 will leads Alice win, so Alice will lose for 3
3 lose -> 4 win
all even number(2,4) smaller than 5 will leads Alice win, so Alice will lose for 5
...

Therefore, Alice will always win for even number, lose for odd number.

X. DP
https://leetcode.com/problems/divisor-game/discuss/274608/Simple-DP-Java-Solution

dp[i] indicates the result of the game for the given number i and for the player who started the game.
Alice will try all factors and choose the one which gives his opponent a losing value.

public boolean divisorGame(int N) {
        boolean[] dp = new boolean[N+1];
        dp[0] = false;
        dp[1] = false;
        for(int i=2; i <= N; i++){
            for(int j=1; j < i; j++){
                if(i % j == 0){
                    if(dp[i-j] == false){
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[N];
    }

https://leetcode.com/problems/divisor-game/discuss/274581/Share-my-stupid-Java-dp-solution

dp[i] represents whether a player can win given the number i if he is the first turn.

class Solution {
    public boolean divisorGame(int N) {
        boolean[] dp = new boolean[N+1];
        for(int i = 1; i <= N; i++){
            for(int x = 1; x < i; x++){
                if(i%x == 0 && !dp[i-x]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }

https://leetcode.com/problems/divisor-game/discuss/274590/C%2B%2B-Recursive-DP

I know, there is a mathematical solution, but in case you did not figure it out :)

int dp[1001] = {};
bool divisorGame(int N, bool res = false) {
  if (dp[N] != 0) return dp[N] == 1;
  for (auto i = 1; !res && i * 2 <= N; ++i) {
    if (N % i == 0) res = !divisorGame(N - i);
  }
  dp[N] = res ? 1 : -1;
  return res;
}