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 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.

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.

Solution

Approach 1: DP.

Approach 2: find a pattern and do an induction proof.

Code (Python)

Approach 1:

class Solution(object):
    def divisorGame(self, N):
        dp = [False for i in range(N+1)]
        dp[1] = False 
        dp[0] = True
        for i in range(2, N + 1):
            for j in range(1, N // 2 + 1):
                if i % j == 0 and (not dp[i - j]):
                    dp[i] = True
                    break
        return dp[-1]

Approach 2:

    def divisorGame(self, N):
        # 1: False
        # 2: True
        # 3: False
        # 4: choose from (1,2) -- 4-3 = 1, False so Alice is True; 4-2 = 2, True so Alice is False -- True
        # 5: choose from (1) -- 5-1 = 4, True so Alice is False -- False
        # Induction:
        # For any even number, can choose 1 so that Bob is left with an odd (False), so Alice can win
        # For any odd number, can only choose odd divisors to substract, resulting in Bob getting an even, so Bob can win, and Alice loses
        return N % 2 == 0

Code (C++)

Approach 1:

Approach 2: