LeetCode 1025. Divisor Game Solution in Java, C++, Python & More

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:

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:

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

PythonJavaC++GoJavaScript

class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0(code-box)