# 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.
Input: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.
Input: 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Approach 1: DP.
Approach 2: find a pattern and do an induction proof.
# Code (Python)
class Solution(object): def divisorGame(self, N): dp = [False for i in range(N+1)] dp = False dp = 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]
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++)