The description of the question is in the following link:
https://leetcode.com/problems/divisor-game/
My Code:
def divisorGame(self, N: int) -> bool:
if N ==1:
return False
else:
ResultList = [0]*(N+1)
ResultList[0] = "Empty"
ResultList[1] = "Lose"
ResultList[2] = "Win" #Here win means that whoever takes this number has a strategy to win with 100%
for i in range(3,N+1):
LoseIndicator = 0
TestNumber = math.ceil(i/2)
for j in range(1,TestNumber+1):
if i/j == i//j:
if ResultList[i-j] == "Lose":
LoseIndicator +=1
if LoseIndicator == 0:
ResultList[i] = "Lose"
else:
ResultList[i] = "Win"
if ResultList[N] =="Win":
return True
else:
return False
Explanation: The win and lose here denotes if the one who chooses this number may win or not. As they are all optimal player, the only time they can win is that under all the situation (with all divisor x), the only choice for the other guy is win, otherwise they may choose the one that lead the opponent to lose.