# 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: