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

A straightforward solution

My first intuition is: every player should try to pick the minimal replacing number.
So this is my first solution, and it’s accepted.

The count variable is used to store the round of game.

class Solution {
public:
    bool divisorGame(int N) {
        int count = 0;
        bool valid = true;
        while(valid) {
            valid = false;
            for(int x = 1; x < N; x++) {
                if(N % x == 0) {
                    N = N - x;
                    count++;
                    valid = true;
                    break;
                }
            }
        }
        return (count % 2 == 1);
    }
};

Recursive Solution

This is a typical recursive problem. We can get the result based on sub-problems.
Assume we have a recursvie_check to check whether Alice will win, the base case is:

• N == 1, Alice will not win, since she can not pick any number
• N == 2, Alice will win, she pick 1, and the competitor don’t have any choices.

So the naïve recursive solution is:

class Solution {
public:
    bool divisorGame(int N) {
        return recursive_check(N);
    }

    bool recursive_check(int n) {
        if(n == 1) return false;
        if(n == 2) return true;

        for(int i=1; i<=n/2; i++) {
            if(n%i == 0 && !recursive_check(n - i)) {
                return true;
            }
        } 
        return false;
    }
};

We will get time-limited error, since there are many duplicated computation(see above diagram). A general solution is add memorization for this recursive function.

If we consider it with the approach of bottom-up, a dynamic programming solution can also solve it.

class Solution {
public:
    map<int, bool> memo;

    bool divisorGame(int N) {
        return recursive_check(N);
    }

    bool recursive_check(int n) {
        if(n == 1) return false;
        if(n == 2) return true;

        auto it = memo.find(n);
        if(it != memo.end()) return it->second;

        for(int i=1; i<=n/2; i++) {
            if(n%i == 0 && !recursive_check(n - i)) {
                memo[n] = true;
                return true;
            }
        } 
        memo[n] = false;
        return false;
    }
};

Mathematical solution

Think carefully with the method of induction, we can get the conclution:

Alice will win for any N%2 == 0.

Yep, Everything is Mathematic! If you are good at math, your code will be sex.

class Solution {
public:
    bool divisorGame(int N) {
        return N % 2 == 0;
    }
};