What is the time complexity of the Dynamic Programming approach?

The time complexity is O(n²) as we iterate through each number and check all possible divisors.

What is the optimal solution for Divisor Game?

The optimal solution is the Mathematical Observation approach with O(1) time and space complexity, which simply checks if n is even.

Why does Alice win only when n is even?

When n is even, Alice can always choose x=1 to give Bob an odd number. Any divisor of an odd number is odd, so Bob must give Alice an even number. This continues until Bob receives 1 and loses.

What is the space complexity of the Memoization approach?

The space complexity is O(n) for the memoization cache plus O(n) for the recursion stack.

Divisor Game | N3mo LC

Difficulty: Easy | Acceptance: 71.80% | Paid: No Topics: Math, Dynamic Programming, Brainteaser, Game Theory

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.

Examples
Constraints
Dynamic Programming
Mathematical Observation
Memoization

Examples

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

Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Constraints

1 <= n <= 1000

Dynamic Programming

Intuition Use a bottom-up DP approach where dp[i] represents whether the current player can win with number i on the board.

Steps

Initialize a dp array of size n+1 with false values.
For each number i from 2 to n, check all possible divisors x.
If there exists a divisor x such that dp[i-x] is false (opponent loses), set dp[i] = true.
Return dp[n] as the result.

python

class Solution:
    def divisorGame(self, n: int) -&gt; bool:
        dp = [False] * (n + 1)
        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
                    break
        return dp[n]

Complexity

Time: O(n²)
Space: O(n)
Notes: Straightforward DP approach but can be optimized mathematically.

Mathematical Observation

Intuition After analyzing the game pattern, Alice wins if and only if n is even. This is because Alice can always force Bob to receive odd numbers.

Steps

Simply check if n is even by using n % 2 == 0.
Return true if even, false if odd.

python

class Solution:
    def divisorGame(self, n: int) -&gt; bool:
        return n % 2 == 0

Complexity

Time: O(1)
Space: O(1)
Notes: Optimal solution based on mathematical insight about parity.

Memoization

Intuition Use top-down recursion with memoization to avoid recomputing results for the same numbers.

Steps

Create a memo dictionary to store computed results.
Define a recursive function that checks if the current player can win with given number.
For each divisor x of the current number, recursively check if opponent loses with n-x.
Use memo to cache results and return the final answer.

python

class Solution:
    def divisorGame(self, n: int) -&gt; bool:
        memo = {}
        
        def canWin(num):
            if num == 1:
                return False
            if num in memo:
                return memo[num]
            
            for x in range(1, num):
                if num % x == 0:
                    if not canWin(num - x):
                        memo[num] = True
                        return True
            
            memo[num] = False
            return False
        
        return canWin(n)

Complexity

Time: O(n²)
Space: O(n)
Notes: Top-down approach with same complexity as bottom-up DP but may have better cache locality.