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.

 
Note:

1 <= N <= 1000

Source: leetcode | Difficulty: EASY
Tags: Dynamic programming

Game theory

Mathematics

Starter code: class Solution:
    def divisorGame(self, N: int) -> bool:
        

Solutions:
class Solution:

	def divisorGame(self, N: int) -> bool:
		return N % 2 == 0


class Solution:

	def divisorGame(self, N: int) -> bool:
		m = 0
		if N > 1:
			for x in range(1, N):
				N -= x
				m += 1
			if m % 2 == 0:
				return False
			else:
				return True


class Solution:
	memo = {}

	def divisorGame(self, N: int) -> bool:
		return self.move(N)

	def move(self, N):
		if N in self.memo:
			return self.memo[N]
		if N == 2:
			return True
		for f in self.factors(N):
			if self.move(N - f) == False:
				self.memo[N] = True
				return True
		self.memo[N] = False
		return False

	def factors(self, n):
		a = []
		for x in range(1, n):
			if n % x == 0:
				a.append(x)
		return a


class Solution:

	def divisorGame(self, N: int) -> bool:
		memo = set()

		def check(factor, player):
			if factor == 1:
				return player != 'A'
			if factor in memo:
				return False
			player = 'A' if player == 'B' else 'B'
			for i in range(1, 1 + factor // 2):
				if factor % i == 0:
					memo.add(factor)
					if check(factor - i, player):
						return True
		return check(N, 'A')


class Solution:

	def divisorGame(self, N: int) -> bool:
		memo = [None] * (N + 1)
		ans = self.canWin(N, memo)
		return ans

	def canWin(self, N, memo):
		if N <= 1:
			return False
		if memo[N] is not None:
			return memo[N]
		for i in range(1, N // 2 + 1):
			if N % i == 0:
				if not self.canWin(N - i, memo):
					memo[N] = True
					return True
		memo[N] = False
		return False


class Solution:

	def divisorGame(self, N: int) -> bool:
		dp = [False for i in range(N + 1)]
		for i in range(N + 1):
			for x in range(1, i // 2 + 1):
				if i % x == 0 and (not dp[i - x]):
					dp[i] = True
					break
		return dp[N]


import math

class Solution:

	def divisorGame(self, N: int) -> bool:
		m = [0 for x in range(N + 1)]
		m[1] = 0
		for x in range(2, N + 1):
			temp = []
			i = 1
			while i < math.sqrt(x):
				if x % i == 0:
					if x / i == i:
						temp.append(i)
					else:
						temp.append(i)
						if x / i != x:
							temp.append(int(x / i))
				i += 1
			for y in temp:
				print(('x-y', x - y))
				if m[x - y] == 0:
					m[x] = 1
		return True if m[N] == 1 else False


class Solution:

	def divisorGame(self, n: int) -> bool:
		return self.helper(n, {})

	def helper(self, n, memo):
		if n == 1:
			return False
		elif n in memo:
			return memo[n]
		else:
			for f in self.factors(n):
				if self.helper(n - f, memo) == False:
					memo[n] = True
					return True
			memo[n] = False
			return False

	def factors(self, n):
		l = []
		i = 1
		while i ** 2 <= n:
			if n % i == 0:
				l.append(i)
			i += 1
		for num in l:
			if num ** 2 < n and num > 1:
				l.append(int(n / num))
		return l


class Solution:

	def divisorGame(self, N: int) -> bool:
		return recurse_game(N, 0)

def find_factors(n):
	factors = []
	for i in range(1, n):
		if n % i == 0:
			factors.append(i)
	return factors
lookup = {}

def recurse_game(N, P):
	if (N, P) in lookup:
		return lookup[N, P]
	if N <= 1 and P == 0:
		lookup[N, P] = False
		return False
	elif N <= 1 and P == 1:
		lookup[N, P] = True
		return True
	next_P = 0 if P == 1 else 1
	results = []
	for factor in find_factors(N):
		results.append(recurse_game(N - factor, next_P))
	if P == 0:
		if True in results:
			lookup[N, P] = True
			return True
		else:
			lookup[N, P] = False
			return False
	if P == 1:
		if False in results:
			lookup[N, P] = False
			return False
		else:
			lookup[N, P] = True
			return True


class Solution:

	def divisorGame(self, N: int) -> bool:
		game = [False for i in range(N + 1)]
		for i in range(2, N + 1):
			for j in range(1, i):
				if i % j == 0 and game[i - j] == False:
					game[i] = True
					break
		return game[N]


class Solution:

	def divisorGame(self, N: int) -> bool:
		if N <= 1:
			return False
		dp = [False] * (N + 1)
		for i in range(2, N + 1):
			for j in range(1, i // 2 + 1):
				if i % j == 0:
					nextN = i - j
					if dp[nextN] == False:
						dp[i] = True
		return dp[N]


def doS(N, arr):
	if N == 1:
		return False
	if not arr[N] == None:
		return arr[N]
	for i in range(1, N):
		if N % i == 0:
			if not doS(N - i, arr):
				arr[i] = True
				return True
	arr[N] = False
	return False

class Solution:

	def divisorGame(self, N: int) -> bool:
		arr = [None] * (N + 1)
		print(arr)
		return doS(N, arr)


class Solution:

	def divisorGame(self, N: int) -> bool:
		table = dict()
		res = self.helper(N, 0, table)
		return res

	def helper(self, N: int, numRds: int, ht: dict) -> bool:
		soln = False
		if N == 1 and numRds % 2 == 0:
			return False
		if N == 1 and numRds % 2 != 0:
			return True
		if ht.get(N, None) != None:
			return ht[N]
		ht[N] = False
		fact = findFactors(N)
		for num in fact:
			ht[N] = ht[N] or self.helper(N - num, numRds + 1, ht)
		return ht[N]

def findFactors(num: int) -> list:
	res = []
	(loPtr, hiPtr) = (1, num)
	while hiPtr > loPtr:
		if num % loPtr == 0:
			res.append(loPtr)
			if num // loPtr != num:
				res.append(num // loPtr)
			hiPtr = num // loPtr
		loPtr += 1
	return res


class Solution:

	@lru_cache(maxsize=None)
	def divisorGame(self, N: int) -> bool:
		if N == 2:
			return True
		options = []
		for x in range(1, N // 2):
			if N % x == 0:
				options.append(N - x)
		return any(map(lambda x: not self.divisorGame(x), options))


class Solution:

	def __init__(self):
		self.memo = {}

	def findfactors(self, N):
		n = N // 2
		fs = []
		for i in range(2, n + 1):
			if N % i == 0:
				fs.append(i)
		return fs + [1]

	def div(self, N):
		if N in self.memo:
			return self.memo[N]
		fs = self.findfactors(N)
		if N == 1:
			self.memo[N] = 0
			return 0
		else:
			nf = len(fs)
			vals = [0] * nf
			for i in range(nf):
				vals[i] = self.div(N - fs[i])
			self.memo[N] = 1 + max(vals)
			return self.memo[N]

	def divisorGame(self, N: int) -> bool:
		ans = self.div(N)
		if ans % 2 == 0:
			return False
		else:
			return True


class Solution:

	def divisorGame(self, N: int) -> bool:
		return N & 1 == 0


class Solution:

	@lru_cache(None)
	def divisorGame(self, N: int) -> bool:
		if N == 0:
			return False
		if N == 1:
			return False
		if N == 2:
			return True

		@lru_cache(None)
		def divs(N):
			out = []
			for i in range(1, N // 2 + 1):
				if N % i == 0:
					out.append(i)
			return out
		moves = divs(N)
		for move in moves:
			if not self.divisorGame(N - move):
				return True
		return False


class Solution:

	def divisorGame(self, N: int) -> bool:
		turns = [{2: 1}, {2: 0}]

		def play(turn, N):
			if N in turns[turn]:
				return turns[turn][N]
			if turn:
				win = all((play(0, N - x) for x in range(1, N) if N % x == 0))
			else:
				win = any((play(1, N - x) for x in range(1, N) if N % x == 0))
			return turns[turn].setdefault(N, win)
		return play(0, N)


from collections import defaultdict as dd

class Solution:

	def __init__(self):
		self.d = dd()

	def divisorGame(self, n: int) -> bool:
		return self.__will_win(n)

	def __will_win(self, n: int):
		for i in range(1, n):
			if n % i != 0:
				continue
			if n - i in self.d:
				wins = self.d[n - i]
			else:
				wins = self.__will_win(n - i)
				self.d[n - i] = wins
			if not wins:
				return True
		return False


class Solution:

	def divisorGame(self, N: int) -> bool:
		if N == 1:
			return False
		elif N == 2:
			return True
		dp = [False for _ in range(N + 1)]
		dp[2] = True
		for a in range(3, N + 1):
			for b in range(1, a):
				if a % b == 0 and dp[a - b] == False:
					dp[a] = True
					break
		return dp[-1]


class Solution:

	def divisorGame(self, N: int) -> bool:
		if N <= 3:
			return N % 2 == 0
		dp = [False for _ in range(N + 1)]
		dp[2] = True
		for i in range(3, N + 1):
			for j in range(1, i):
				if i % j == 0 and dp[i - j] == False:
					dp[i] = True
					break
		return dp[-1]


class Solution:

	@lru_cache(None)
	def divisorGame(self, N: int) -> bool:
		if N == 1:
			return False
		return any((not self.divisorGame(N - x) if N % x == 0 else False for x in range(1, N)))


class Solution:

	def divisorGame(self, N: int) -> bool:
		self.visited = collections.defaultdict(bool)

		def alice_wins(N, alice=True):
			if N == 1:
				return True if not alice else False
			if N in self.visited:
				return self.visited[N]
			for i in range(1, N):
				if not N % i:
					if alice:
						self.visited[N] = alice_wins(N - i, alice=False)
					else:
						self.visited[N] = alice_wins(N - i)
			return self.visited[N]
		return alice_wins(N)


class Solution:

	def divisorGame(self, N: int) -> bool:
		if N % 2 == 0:
			return True
		else:
			return False


class Solution:

	def divisorGame(self, N: int) -> bool:
		table = dict()
		res = self.helper(N, 0, table)
		return res

	def helper(self, N: int, numRds: int, ht: dict) -> bool:
		soln = False
		if N == 1 and numRds % 2 == 0:
			return False
		if N == 1 and numRds % 2 != 0:
			return True
		if ht.get(N, None) != None:
			a = 5
			return ht[N]
		fact = findFactors(N)
		ht[N] = False
		for num in fact:
			ht[N] = ht[N] or self.helper(N - num, numRds + 1, ht)
		return ht[N]

def findFactors(num: int) -> list:
	res = []
	for val in range(1, num):
		if num % val == 0:
			res.append(val)
	return res


class Solution:

	def divisorGame(self, N: int) -> bool:
		d = {}

		def dp(v):
			if v not in d:
				d[v] = False
				for w in range(1, v):
					if v % w == 0:
						d[v] = d[v] or not dp(v - w)
			return d[v]
		out = dp(N)
		return out


class Solution:

	def divisorGame(self, N: int) -> bool:
		res = [False] * (N + 1)
		for i in range(2, N + 1):
			if i % 2 == 0 and res[int(i / 2)] == False:
				res[i] = True
				continue
			for j in range(1, int(math.sqrt(i))):
				if i % j == 0:
					if res[i - j] == False or (j != 1 and res[i - int(i / j)] == False):
						res[i] = True
						break
		return res[N]


class Solution:

	def divisorGame(self, N: int) -> bool:
		dp = [False, False]
		for x in range(2, N + 1):
			dp.append(any([not dp[x - i] for i in range(1, int(math.sqrt(x)) + 1) if x % i == 0]))
		return dp[-1]


class Solution:

	def divisorGame(self, N: int) -> bool:
		return win_game(N)
from functools import lru_cache

@lru_cache(maxsize=None)
def win_game(N):
	return any((not win_game(N - x) for x in range(1, N) if N % x == 0))


class Solution:

	def divisorGame(self, N: int) -> bool:

		def divisors(N):
			if N == 1:
				return [1]
			res = []
			for n in range(1, int(N ** 0.5) + 1):
				if N % n == 0:
					res.append(n)
			return res
		table = {1: False, 2: True, 3: False}

		def compute(i):
			if i in table:
				return table[i]
			divs = divisors(i)
			next_nums = [i - d for d in divs]
			for n in next_nums:
				status = compute(n)
				if status == False:
					table[i] = True
					return True
			table[i] = False
			return False
		return compute(N)