Formatted question description: https://leetcode.ca/all/1025.html
1025. Divisor Game (Easy)
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: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
Input: 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Note:
1 <= N <= 1000
Companies:
Visa
Related Topics:
Math, Dynamic Programming
Solution 1.
// OJ: https://leetcode.com/problems/divisor-game/
// Time: O(N * sqrt(N))
// Space: O(N)
class Solution {
private:
unordered_map<int, bool> m;
public:
bool divisorGame(int N) {
if (N == 1) return false;
if (m.find(N) != m.end()) return m[N];
bool ans = false;
for (int x = sqrt(N); x >= 1 && !ans; --x) {
if (N % x) continue;
if (!divisorGame(N - x)) ans = true;
}
return m[N] = ans;
}
};
Solution 2.
Denote F(N)
as the result.
- If
F(N) = false
, thenF(N + 1) = true
. Because for caseN + 1
, Alice can simply pickx = 1
to win. - If
N
is odd number, it only have odd factors. So after the first move, it will become even number.
F(1) = false
F(2) = true
according to Rule #1.F(3) = false
since2
is the only possible situation for Bob andF(2) = true
.F(4) = true
according to Rule #1.F(5) = false
since all even numbers (2
and4
) lead totrue
for Bob.- …
So we can see, even numbers always win; odd numbers lose.
// OJ: https://leetcode.com/problems/divisor-game/
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/divisor-game/discuss/274566/just-return-N-2-0-(proof)
class Solution {
public:
bool divisorGame(int N) {
return N % 2 == 0;
}
};
Java
-
class Solution { public boolean divisorGame(int N) { boolean[] dp = new boolean[N + 1]; for (int i = 1; i <= N; i++) { for (int j = 1; j < i; j++) { if (i % (i - j) == 0 && !dp[j]) { dp[i] = true; break; } } } return dp[N]; } }
-
// OJ: https://leetcode.com/problems/divisor-game/ // Time: O(N * sqrt(N)) // Space: O(N) class Solution { private: unordered_map<int, bool> m; public: bool divisorGame(int N) { if (N == 1) return false; if (m.find(N) != m.end()) return m[N]; bool ans = false; for (int x = sqrt(N); x >= 1 && !ans; --x) { if (N % x) continue; if (!divisorGame(N - x)) ans = true; } return m[N] = ans; } };
-
# 1025. Divisor Game # https://leetcode.com/problems/divisor-game/ class Solution: def divisorGame(self, n: int) -> bool: return n % 2 == 0