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.
count variable is used to store the round of game.
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.
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.