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 subproblems.
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 timelimited 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 bottomup, 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.

Join my Email List for more insights, It's Free!😋