# Leetcode: Divisor Game

Divisor Game

Similar Problems:

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:

1. Choosing any x with 0 < x < N and N % x == 0.
2. 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.

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution: dynamic programming
```// Blog link: https://code.dennyzhang.com/divisor-game
// Basic Ideas: dynamic programming
// Complexity: Time O(1), Space O(1)
func divisorGame(N int) bool {
dp := make([]bool, N+1)
dp[1] = false
for i:=2; i<=N; i++ {
dp[i] = false
for j:=1; j<i; j++ {
if i%j == 0 {
if dp[i-j] == false {
dp[i] = true
break
}
}
}
}
return dp[N]
}
```

• Solution: pruned dynamic programming
```// Blog link: https://code.dennyzhang.com/divisor-game
// Basic Ideas: dynamic programming
// Complexity: Time O(1), Space O(1)
func check(N int, dp map[int]bool) bool {
status, ok := dp[N]
if ok == true {
return status
}
for i:=1; i<N && N%i == 0; i++ {
if check(N-i, dp) == false {
dp[N] = true
return true
}
}
dp[N] = false
return false
}

func divisorGame(N int) bool {
dp := map[int]bool{}
return check(N, dp)
}
```

Share It, If You Like It.