1025. Divisor Game
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
with0 < x < n
andn % x == 0
. - Replacing the number
n
on the chalkboard withn - 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: n = 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
Input: n = 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Constraints:
1 <= n <= 1000
Solutions
Solution 1: Mathematical Induction
- When $n=1$, the first player loses.
- When $n=2$, the first player takes $1$, leaving $1$, the second player loses, the first player wins.
- When $n=3$, the first player takes $1$, leaving $2$, the second player wins, the first player loses.
- When $n=4$, the first player takes $1$, leaving $3$, the second player loses, the first player wins.
- ...
We conjecture that when $n$ is odd, the first player loses; when $n$ is even, the first player wins.
Proof:
- If $n=1$ or $n=2$, the conclusion holds.
- If $n \gt 2$, assume that the conclusion holds when $n \le k$, then when $n=k+1$:
- If $k+1$ is odd, since $x$ is a divisor of $k+1$, then $x$ can only be odd, so $k+1-x$ is even, the second player wins, the first player loses.
- If $k+1$ is even, now $x$ can be either odd $1$ or even. If $x$ is odd, then $k+1-x$ is odd, the second player loses, the first player wins.
In conclusion, when $n$ is odd, the first player loses; when $n$ is even, the first player wins. The conclusion is correct.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 |
|