Divisor Game - Leetcode Solution

Problem statement: 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:

Input: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.

Solution:

Approach: The approach to solve this problem is based on Dynamic Programming. The task is to determine whether Alice can win or not if they make the optimal move in each turn. To determine the optimal move, we need to find all the valid divisors of the current number and then select one of the divisors that maximizes the chance of winning. A brute-force approach will be to use recursion with memoization to store the previous values of the function.

Algorithm:

Create a recursive function with parameters N and a bool variable that keeps track of the current player. If N == 1, return False, as one cannot make any moves. If N < 1, there is no feasible move, and the current player loses, return False. If the current player is Alice, we need to consider all the valid divisors of N. For each divisor x, call the function recursively with (N - x, Bob). If the function returns False, then Alice can win by selecting this move, so return True. Similarly, if the current player is Bob, then for each divisor x of N, call the function recursively with (N - x, Alice). If the function returns False, then Bob can win with this move, so return True. If we have checked all the possible moves for the current player, and still we have not returned any value, then the current player cannot make any feasible move, and so they lose the game, return False. Now, we only need to call the recursive function with (N, Alice), and check the returned value.

Source code:

class Solution: def divisorGame(self, N: int) -> bool: memo = {}

    def can_win(n, who):
        if n == 1:
            return False
        if n < 1:
            return False
        if (n, who) in memo:
            return memo[(n, who)]
        if who == 'Alice':
            for x in range(1, n):
                if n % x == 0:
                    if not can_win(n - x, 'Bob'):
                        memo[(n, who)] = True
                        return True
            memo[(n, who)] = False
            return False
        else:
            for x in range(1, n):
                if n % x == 0:
                    if not can_win(n - x, 'Alice'):
                        memo[(n, who)] = True
                        return True
            memo[(n, who)] = False
            return False

    return can_win(N, 'Alice')

Time Complexity: O(N²), as there can be up to N iterations, and for each iteration, we need to find all divisors of the current number.

Space Complexity: O(N), as we need to store all the previous values in the memo dictionary.

1