 # Rocket Academy Divisor Game Solution

Mar 24th, 2021
910
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # https://leetcode.com/problems/divisor-game/
2. class Solution:
3.
4.     def __init__(self):
5.         # Keys will be value of N
6.         # Values will be can curr_player win
7.         self.cache = {}
8.
9.     def determine_if_alice_can_win(self, N, curr_player):
10.         # Base case
11.         # If N and curr_player in cache, return cached value
12.         if N in self.cache:
13.             if curr_player == 0:
14.                 if self.cache[N] == True:
15.                     return True
16.                 return False
17.
18.             # If curr player is Bob
19.             if self.cache[N] == True:
20.                 return False
21.             return True
22.
23.         # If N is 1, current player loses
24.         if N == 1:
25.             if curr_player == 0:
26.                 return False
27.             return True
28.
29.         # For each number num between 1 and N/2 inclusive:
30.         for num in range(1, N//2 + 1):
31.             # Skip if N is not multiple of num
32.             if N % num != 0:
33.                 continue
34.
35.             # If N is multiple of num: Recurse and tell me if Alice can win if curr player chooses num
36.             next_player = (curr_player + 1) % 2
37.             can_alice_win = self.determine_if_alice_can_win(N-num, next_player)
38.
39.             # If calculation is not in cache yet, add it to the cache
40.             if N-num not in self.cache:
41.                 if next_player == 0:
42.                     self.cache[N-num] = can_alice_win
43.                 else:
44.                     self.cache[N-num] = not can_alice_win
45.
46.             # If current player is Alice AND Alice can win, return True
47.             if curr_player == 0 and can_alice_win:
48.                 return True
49.
50.             # If current player is Bob AND Alice CANNOT win for any 1 of the values of num, return False
51.             if curr_player == 1 and not can_alice_win:
52.                 return False
53.
54.         # If current player is Alice and she hasn't won yet, return False
55.         if curr_player == 0:
56.             return False
57.
58.         # If current player is Bob and Alice hasn't lost yet, return True
59.         if curr_player == 1:
60.             return True
61.
62.     def divisorGame(self, N: int) -> bool:
63.         # Return whether A wins for original N
64.         # Player 0 represents A, Player 1 represents B
65.         return self.determine_if_alice_can_win(N, 0)