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

Difficulty: introductory

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:
        dp = [False for i in range(N+1)]
        for i in range(N+1):
            for j in range(1, i//2+1):
                if i % j == 0 and (not dp[i - j]):
                    dp[i] = True
                    break
        return dp[N]



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))
        
    # print(N,P,results)
        
    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:
        return N % 2 == 0

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]

class Solution:
    def divisorGame(self, N: int) -> bool:
        dp = [False for _ in range(N+1)]
        
        for i in range(N+1):
            for j in range(1, i//2+1):
                # dp[i-j] make sure Bob fails at step i-j
                if i % j == 0 and dp[i-j] == False:
                    dp[i] = True
        
        return dp[-1]

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
                # print(N-i,arr)  
                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
        
        # Bob wins base case
        if N == 1 and numRds % 2 == 0: return False 
        
        # Alice wins base case
        if N == 1 and numRds % 2 != 0: return True
        
        # Check to see if the current N values has been processed
        if ht.get(N, None) != None: return ht[N]
        ht[N] = False
        # Obtain list of factors
        fact = findFactors(N)
        
        # If not in the table process N against all of its factors
        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:
    def divisorGame(self, N: int) -> bool:
        dp = [False] * (N + 1)
        for i in range(N + 1):
            for j in range(1, i//2 + 1):
                if i%j == 0 and not dp[i - j]:
                    dp[i] = True
                    break
        return dp[-1]


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:
    
    #this function will return all the possible nums after one move
    
    
    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: 
                # this player choses this i as the next one will lose
                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:
        dp = [False]*(N+1)
        for i in range(2,N+1):
            j = 1
            while j<i:
                if i%j==0 and dp[i-j]==False:
                    dp[i] = True
                    break
                j+=1          
        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:
    def divisorGame(self, N: int) -> bool:
        if N == 1:
            return False
        elif N == 2:
            return True
        
        dp = [False]*(N+1)
        dp[1] = True
        dp[2] = True
        
        for i in range(3, N+1):
            for j in range(1, i):
                if i%2 == 0:
                    dp[i] = True
                    break
        print(dp)
        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:
        if N<2:
            return False
        dp=[False]*(N+1)
        dp[2]=True
        
        for i in range(2,N+1):
            for x in range(1,i):
                if i%x==0 and not dp[i-x]:
                    dp[i]=True
        return dp[-1]


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
        
        # Bob wins base case
        if N == 1 and numRds % 2 == 0: return False 
        
        # Alice wins base case
        if N == 1 and numRds % 2 != 0: return True
        
        # Check to see if the current N values has been processed
        if ht.get(N, None) != None: 
            a = 5
            return ht[N]
        
        # Obtain list of factors
        fact = findFactors(N)
        
        # If not in the table process N against all of its factors
        ht[N] = False        # Base case to ensure no false positives
        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:
    # dp solution
    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
        
        # Initial conditions
        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
        
        
#         for n in range(3, N+1):
#             divs = divisors(n)
            
#             for d in divs:
#                 next_num = n - d
#                 if table[next_num] == False:
#                     # We want the next number to be a losing number
#                     table[n] = True
#                     break
#             if n not in table:
#                 # If all next numbers are winning, then this is a losing number
#                 table[n] = False

        return compute(N)