Problem#
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 .
Examples#
Example 1:
1
2
3
Input: n = 2
Output: true
Explanation: Alice chooses 1 , and Bob has no more moves.
Example 2:
1
2
3
Input: n = 3
Output: false
Explanation: Alice chooses 1 , Bob chooses 1 , and Alice has no more moves.
Solution#
Method 1 – Mathematical Parity#
Intuition#
If n is even, Alice can always win by making n odd for Bob. If n is odd, Bob will always win by making n even for Alice. This is because every move reduces n by an odd divisor, flipping the parity.
Approach#
If n is even, Alice wins.
If n is odd, Bob wins.
Return n % 2 == 0.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
class Solution {
public :
bool divisorGame(int n) {
return n % 2 == 0 ;
}
};
1
2
3
func divisorGame (n int ) bool {
return n % 2 == 0
}
1
2
3
4
5
class Solution {
public boolean divisorGame (int n) {
return n % 2 == 0;
}
}
1
2
3
4
5
class Solution {
fun divisorGame (n: Int): Boolean {
return n % 2 == 0
}
}
1
2
3
class Solution :
def divisorGame (self, n: int) -> bool:
return n % 2 == 0
1
2
3
4
5
impl Solution {
pub fn divisor_game (n: i32 ) -> bool {
n % 2 == 0
}
}
1
2
3
4
5
class Solution {
divisorGame (n : number ): boolean {
return n % 2 === 0 ;
}
}
Complexity#
⏰ Time complexity: O(1)
— Only a parity check.
🧺 Space complexity: O(1)
— No extra space used.