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)
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.