Algorithm
Problem Name: 1025. Divisor Game
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
xwith0 < x < nandn % x == 0. - Replacing the number
non 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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean divisorGame(int N) {
boolean[] dp = new boolean[N + 1];
dp[0] = false;
dp[1] = false;
for (int i = 2; i < = N; i++) {
for (int j = 1; j < i; j++) {
if (i % j == 0) {
if (dp[i - j] == false) {
dp[i] = true;
break;
}
}
}
}
return dp[N];
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const divisorGame = function(N) {
let idx = 0
let x
while(x = chk(N)) {
idx++
N = N - x
}
if(idx === 0) return false
return idx % 2 === 1 ? true : false
};
function chk(num) {
for(let i = 1; i < num; i++) {
if(num % i === 0> return i
}
return false
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def divisorGame(self, N: int) -> bool:
return N % 2 == 0
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _1025_DivisorGame
{
public bool DivisorGame(int N)
{
if (N == 1) return false;
if (N == 2) return true;
var result = new bool[N + 1];
result[1] = false;
result[2] = true;
for (int i = 3; i < = N; i++)
{
var bobWin = true;
for (int j = 1; j < = i / 2; j++)
{
if (i % j == 0)
bobWin = bobWin && result[i - j];
if (!bobWin) break;
}
result[i] = !bobWin;
}
return result[N];
}
}
}
Input
Output