Scale Engineer

Divisor Game

Easy
#0979Time: 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: O(n) to store the results for `n` subproblems in the DP array.1 company
Patterns
MathDynamic ProgrammingGame Theory
Companies
Visa

Prompt

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

2 approaches with complexity analysis and trade-offs.

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].

Walkthrough

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

Time

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

O(n) to store the results for `n` subproblems in the DP array.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem