Advertisement
kai-rocket

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)
Advertisement
RAW Paste Data Copied
Advertisement