1025. Divisor Game

EasyBrainteaserMathDynamic ProgrammingGame Theory

Problem Description

Alice and Bob are playing a game that involves numbers and strategy. In this game, they take turns with Alice starting first. They have a number n initialized on the chalkboard. Each turn, the current player must perform the following actions:

Choose any positive number x such that x is less than n and n % x == 0, which means x has to be a divisor of n (n is divisible by x without any remainder).
Then they must replace the number n on the chalkboard with n - x.

The game continues until a player can no longer make a move. That happens when n becomes 1, because there are no numbers less than 1 which divide 1, hence no legal move is possible. The player who cannot make a move loses the game.

The objective of this problem is to determine if Alice can win the game, given that both Alice and Bob play with optimal strategies. We return true if Alice can win and false if she cannot.

Intuition

To determine if Alice can win the game given the number n, we look for a pattern or strategy that can guarantee a win. Analyzing the outcomes of the first few even and odd values of n can give us some insight:

If n is an odd number, then all divisors of n are also odd. Subtracting an odd number from an odd number always results in an even number. So if Alice starts with an odd number, Bob will always receive an even number.
If n is an even number, Alice can always subtract 1 (which is a legal move because 1 is a divisor of all numbers), resulting in an odd number for Bob's turn.

Following these steps optimally, whenever Alice starts with an even number, she can always make a move that leaves an odd number to Bob. Since Bob then can only subtract odd divisors and return an even number back to Alice, this process repeats until Bob is eventually left with the number 1 and no legal moves, resulting in a loss for Bob.

Therefore, we can say that if n is even, Alice can win by following the strategy of always subtracting 1, ensuring Bob always gets an odd number. Conversely, if n is odd, Bob will be able to follow the same strategy against Alice when he gets his turn, and Alice will eventually lose. So the intuition behind the solution is that Alice wins if and only if she starts with an even number.

The solution is quite simple and elegant when we understand this pattern. The code checks whether the initial number n is even and returns true if it is and false otherwise, which can be achieved with a single line of code by checking n % 2 == 0.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The implementation of the solution for Alice and Bob's game is surprisingly straightforward and does not require complex algorithms or data structures because the problem boils down to an insight into number parity (whether a number is even or odd) rather than an exhaustive search or some dynamic programming approach.

The pattern observed during the Intuition step is that if Alice starts with an even number (n % 2 == 0), she will win the game following the optimal strategy of reducing the number by 1 each time her turn arrives. This move ensures that Bob always gets an odd number and cannot force Alice into a losing position.

The solution code uses this insight directly:

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

In this code:

The divisorGame method takes an integer n.
It returns the Boolean value True if n is even, indicating that Alice can win.
If n is odd, it returns False, indicating that Alice will lose if both players play optimally.

No additional data structures or algorithms are needed because the problem does not ask us to keep track of the game state or the sequence of moves, only to determine the winner based on the initial value of n.

By reducing the problem to a simple evaluation of whether the input number n is even or odd, we can implement a constant-time solution (O(1) time complexity) with constant space (O(1) space complexity), which is highly efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an example where n = 4 which is an even number to illustrate the solution approach:

Turn 1 (Alice's turn): n = 4. Alice can choose x = 1 (since 1 is a divisor of 4), and then replace n with n - x, which is 4 - 1 = 3. Now n = 3.
Turn 2 (Bob's turn): n = 3. Bob can only choose odd divisors, and let's say he chooses x = 1 again (the only divisor he can choose other than 3 itself), resulting in n - x = 2. Now n = 2.
Turn 3 (Alice's turn): n = 2. Alice, following the optimal strategy, chooses x = 1, leaving n at 2 - 1 = 1. Now n = 1.
Turn 4 (Bob's turn): n = 1. Bob has no legal moves because the only divisor of 1 is 1 itself, but the rule states that the chosen number x must be less than n. Thus, Bob cannot make a move and loses the game.

As we can see, during her turn, Alice can always make sure to leave an odd number for Bob by choosing x = 1, following the optimal strategy. Since the only even divisor of an odd number is 1, and subtracting it will always result in an even number, Alice can repeat this process until Bob is left with the inevitable position of n = 1, causing him to lose.

This walkthrough demonstrates that for any even starting number n, Alice can win the game by making sure to subtract 1 on each of her turns. This strategy is fully encapsulated by the given code:

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

This code returns True for our example where n = 4, which indicates that Alice can indeed win if she starts with an even number and both players play optimally.

Solution Implementation

1class Solution:
2    def divisor_game(self, n: int) -> bool:
3        # Check if the given number n is even.
4        # The main strategy relies on the fact that Alice will always win if she
5        # starts with an even number. This happens because Alice can always subtract 1
6        # to give Bob an odd number. Odd numbers always have odd divisors (except 1),
7        # so Bob will return an even number back to Alice.
8        # If Alice starts with an odd number, she can only make the number even,
9        # and Bob will then be able to keep giving odd numbers back to her.
10        # Eventually leading to Alice's loss when the number is reduced to 1.
11        return n % 2 == 0
12
13# The name of the method should match with the initial given name, which is `divisorGame`, 
14# so the method name remains unchanged to maintain compatibility with any code that might use this class.
15# Note that the commentary provides an insight into why the method works and what the game strategy is,
16# based on the problem statement likely provided in a corresponding LeetCode problem.
17

1class Solution {
2  
3    /**
4     * Determines if the player who starts the game will win the divisor game given the number n.
5     *
6     * @param n The starting number for the divisor game.
7     * @return True if the starting player wins the game; otherwise, false.
8     */
9    public boolean divisorGame(int n) {
10        // In the divisor game, the player who starts with an even number wins.
11        // This is because they can always subtract 1 (an optimal move),
12        // giving the other player an odd number. Odd numbers always have odd divisors (except 1),
13        // so the other player can only return an even number back.
14        // The starting player can continue this strategy until they reach the number 2 and win the game.
15        // If the starting number is odd, the starting player loses because they can only make
16        // the number even for the other player, who will then start using the winning strategy.
17        return n % 2 == 0;
18    }
19}
20

1class Solution {
2public:
3    // Determines if the starting player of the Divisor Game will win.
4    // The Divisor Game rules are as follows:
5    // - Two players take turns picking a number x where 0 < x < n and n % x == 0.
6    // - The player that chooses x subtracts it from n to form a new n.
7    // - The player who cannot make a move (because no such x exists) loses.
8    // According to the problem, Alice starts first, and if n is even, she can win by playing optimally.
9    bool divisorGame(int N) {
10        // The strategy here is based on the mathematical deduction that the
11        // player who starts with an even number can always win by halving the number.
12        // If 'N' is even, the current player will win.
13        // If 'N' is odd, the next player will eventually get an even 'N' and win.
14        return N % 2 == 0;
15    }
16};
17

1// Determines if the starting player of the Divisor Game will win.
2// The game rules are as follows:
3// - Two players take turns picking a number x where 0 < x < n and n % x == 0.
4// - The player that chooses x subtracts it from n to form a new n.
5// - The player who cannot make a move (because no such x exists) loses.
6// Since Alice starts first, and if n is even, she can always win by playing optimally.
7function divisorGame(N: number): boolean {
8    // Optimally, the starting player (Alice) who begins with an even 'N'
9    // can continue to subtract 1 (an optimal x) and hand over an odd number to the opponent.
10    // This ensures that the opponent always gives back an even number
11    // because odd - even = odd, and she can keep subtracting 1.
12    // Eventually, Alice will give '2' to the opponent, who will then only
13    // be able to subtract '1' and hand back '1', at which point they will lose
14    // because no x exists that divides '1' (other than '1' itself, which is not allowed).
15    // Thus, the initial parity of 'N' determines the game's outcome.
16    return N % 2 === 0;
17}
18

Time and Space Complexity

Time Complexity:

The given Python function divisorGame consists of a single operation that checks whether the input integer n is even. This check is performed in constant time. Therefore, the time complexity of this function is O(1).

Space Complexity:

The function does not utilize any additional data structures that grow with the input size. Since it only uses a fixed amount of space to store the input and output values, the space complexity is also constant. Hence, the space complexity of the function is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know