 Coder's Cat

2020-11-21

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

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

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