Divisor Game

EASY

Description

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 1:

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

Example 2:

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

Constraints:

1 <= n <= 1000

Approaches

Checkout 2 different approaches to solve Divisor Game. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

This approach uses dynamic programming to solve the game. We determine the winner for each number i from 1 up to n. A player wins from a state i if they can make a move to a state j from which the other player is guaranteed to lose.

Algorithm

Create a boolean DP array dp of size n + 1, initialized to false.
Loop i from 2 to n.
Inside this loop, loop x from 1 to i-1.
If i is divisible by x, check the value of dp[i - x].
If dp[i - x] is false, it means we found a move to a losing position for the opponent. Set dp[i] = true and break the inner loop.
After the loops complete, return dp[n].

We can solve this game theory problem using a bottom-up dynamic programming approach. The state of the game is defined by the current number n on the chalkboard.

Let dp[i] be a boolean value indicating if the current player can win starting with the number i.

dp[i] = true means the current player can win.
dp[i] = false means the current player will lose if the opponent plays optimally.

The goal is to compute dp[n].

Base Case: For n = 1, there are no valid moves (0 < x < 1 is impossible). So, the player whose turn it is loses. dp[1] = false.
Transitions: For any number i > 1, the current player wins if they can make a move to a number i - x (where x is a proper divisor of i) from which the other player loses. In other words, dp[i] is true if there exists a divisor x of i such that dp[i - x] is false.

We can build up the dp table from i = 2 to n.

class Solution {
    public boolean divisorGame(int n) {
        boolean[] dp = new boolean[n + 1];
        // In Java, boolean arrays are initialized to false.
        // So dp[1] is already false.
        
        for (int i = 2; i <= n; i++) {
            for (int x = 1; x < i; x++) {
                if (i % x == 0) {
                    // Check if moving to i-x is a winning move.
                    // A move is winning if the opponent is left in a losing state.
                    // A losing state for the opponent is one where dp[state] is false.
                    if (!dp[i - x]) {
                        dp[i] = true;
                        break; // Found a winning move, no need to check further for this i.
                    }
                }
            }
        }
        return dp[n];
    }
}

Complexity Analysis

Time Complexity: O(n^2). The outer loop runs `n` times, and the inner loop runs up to `n` times for each `i`. This gives a quadratic time complexity.Space Complexity: O(n) to store the results for `n` subproblems in the DP array.

Pros and Cons

Pros:

It's a general and intuitive approach for solving impartial games.
Guaranteed to find the optimal solution.

Cons:

Not the most efficient solution for this specific problem.
The O(n^2) time complexity might be too slow for larger n, but it's acceptable for n <= 1000.

Code Solutions

Checking out 4 solutions in different languages for Divisor Game. Click on different languages to view the code.

class Solution {
public
  boolean divisorGame(int n) { return n % 2 == 0; }
}

Video Solution

Watch the video walkthrough for Divisor Game

Patterns:

MathDynamic ProgrammingGame Theory

Companies:

Visa |