Jobs

Interviews

Discussions

Divisor Game

Easy

Visa

1 view

Topics:

Dynamic ProgrammingGreedy Algorithms

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

Divisor Game

Easy

Visa

1 view

Topics:

Dynamic ProgrammingGreedy Algorithms

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for `n`? Is `n` always a positive integer?
If `n` is 1 initially, Alice cannot make a move, so she loses. Is that correct?
Is there any situation in which the game might run indefinitely? Should I be concerned about preventing infinite loops?
Is it guaranteed that `n` will be an integer, or should I handle other potential data types?
Are we aiming for a solution that works efficiently for very large values of `n` (e.g., up to 10^9 or beyond)?

Brute Force Solution

Approach

The brute force method for this game is like exploring every single possible move and outcome. We play the game out in our mind step by step, trying every allowed choice at each turn. We continue this process until we find a winning strategy for the first player, or until we've exhausted all possibilities.

Here's how the algorithm would work step-by-step:

Start with the given number.
Find all the numbers that divide evenly into the current number.
For each of those divisors, imagine the first player chooses that divisor and subtracts it from the current number.
Now, consider the second player's turn with the new number.
Again, find all the divisors of the new number.
For each of these divisors, imagine the second player chooses that divisor and subtracts it from the new number.
Continue this process, alternating turns between the first and second player, until someone reaches zero and wins.
Keep track of which choices lead to a win for the first player.
If, after trying every possible move and counter-move, you find a path where the first player always wins, then the first player can win the game. Otherwise, the first player loses.

Code Implementation

def divisor_game_brute_force(number):
    def can_win(current_number, is_alice_turn):
        # Base case: If number is 0, the other player won
        if current_number == 0:
            return not is_alice_turn

        divisors = []
        for possible_divisor in range(1, current_number + 1):
            if current_number % possible_divisor == 0:
                divisors.append(possible_divisor)

        #If no divisors, the current player loses
        if not divisors:
            return False

        # Try all divisors and see if any lead to a win
        for divisor in divisors:
            next_number = current_number - divisor

            # Recursively check if the other player loses with the next number
            if not can_win(next_number, not is_alice_turn):
                return True

        # If no move leads to a win, the current player loses
        return False

    #Alice is the first to make a move
    return can_win(number, True)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force solution explores every possible move, which can be visualized as a decision tree. At each step, we find all divisors of the current number 'n'. In the worst case, the number of divisors can be substantial and for each divisor, we create a new branch in the decision tree. Since the game can continue for a number of turns related to 'n', and at each turn we could have multiple divisor choices leading to branching, the total number of possible game states explored grows exponentially. Therefore the time complexity approximates O(2^n), reflecting the exponential growth of the decision tree.

Space Complexity

O(N) – The brute force method, as described, involves exploring every possible move and outcome, which can be visualized as a decision tree. In the worst-case scenario, the depth of this tree can be proportional to N, where N is the initial number. To keep track of the explored states and the path taken, we could implicitly use a recursion stack or a similar data structure, resulting in a maximum space usage proportional to the depth of the recursion, which is N. Thus, the space complexity is O(N).

Optimal Solution

Approach

The core idea is to determine who wins based on the starting number. We can figure this out without actually playing the game by recognizing a simple pattern. The winner is predictable based on whether the starting number is odd or even.

Here's how the algorithm would work step-by-step:

Think about what happens with small numbers. If the starting number is 1, the first player loses immediately.
If the starting number is even, the first player can always win. They pick a factor that makes the remaining number odd. The second player is then forced to pick an odd number, resulting in an even number after subtraction. This repeats, always giving the first player an even number to work with until the second player is left with the number 1.
If the starting number is odd, the first player can only pick odd factors, leaving an even number for the second player. Now the second player is in the same winning position as the first player was with an even number. The second player can then force the first player to eventually be left with 1.
Therefore, if the starting number is even, the first player wins. If it is odd, the first player loses.

Code Implementation

def divisor_game(number):
    # If the starting number is even, Alice wins.
    if number % 2 == 0:
        return True

    # If the number is 1, Alice loses

    # If the starting number is odd, Alice loses.
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The solution's approach directly determines the winner based on whether the input number 'n' is even or odd. This involves a single conditional check. Since this check takes constant time regardless of the value of n, the time complexity is O(1).

Space Complexity

O(1) – The provided explanation infers a direct calculation based on whether the input number N is even or odd. It does not mention creating any auxiliary data structures like arrays, lists, or hash maps. Consequently, the algorithm uses only a fixed amount of extra memory, regardless of the value of N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
n = 1	Alice loses immediately as there are no divisors x such that 0 < x < 1, so return false.
n = 2	Alice chooses x = 1, n becomes 1, Bob loses; therefore, Alice wins so return true.
Large values of n	Memoization or dynamic programming is necessary to avoid exponential time complexity from repeated calculations for the same n.
n is a prime number	Alice can only choose 1, reducing n to n-1, and the game continues depending on n-1.
n is a power of 2	This can influence the win/loss pattern; the solution should correctly determine the outcome through the game's rules.
Recursion depth exceeding limits without memoization	If the approach is recursive, ensure memoization is used to prevent stack overflow errors for large values of n.
Integer overflow when calculating n - x	The problem statement guarantees n is an integer so integer overflow is not a concern for subtraction given that x < n.
Time Limit Exceeded (TLE) for large n without optimization	Ensure the solution uses efficient algorithms like dynamic programming or memoization to reduce time complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for `n`? Is `n` always a positive integer?
If `n` is 1 initially, Alice cannot make a move, so she loses. Is that correct?
Is there any situation in which the game might run indefinitely? Should I be concerned about preventing infinite loops?
Is it guaranteed that `n` will be an integer, or should I handle other potential data types?
Are we aiming for a solution that works efficiently for very large values of `n` (e.g., up to 10^9 or beyond)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the given number.
Find all the numbers that divide evenly into the current number.
For each of those divisors, imagine the first player chooses that divisor and subtracts it from the current number.
Now, consider the second player's turn with the new number.
Again, find all the divisors of the new number.
For each of these divisors, imagine the second player chooses that divisor and subtracts it from the new number.
Continue this process, alternating turns between the first and second player, until someone reaches zero and wins.
Keep track of which choices lead to a win for the first player.
If, after trying every possible move and counter-move, you find a path where the first player always wins, then the first player can win the game. Otherwise, the first player loses.

Code Implementation

def divisor_game_brute_force(number):
    def can_win(current_number, is_alice_turn):
        # Base case: If number is 0, the other player won
        if current_number == 0:
            return not is_alice_turn

        divisors = []
        for possible_divisor in range(1, current_number + 1):
            if current_number % possible_divisor == 0:
                divisors.append(possible_divisor)

        #If no divisors, the current player loses
        if not divisors:
            return False

        # Try all divisors and see if any lead to a win
        for divisor in divisors:
            next_number = current_number - divisor

            # Recursively check if the other player loses with the next number
            if not can_win(next_number, not is_alice_turn):
                return True

        # If no move leads to a win, the current player loses
        return False

    #Alice is the first to make a move
    return can_win(number, True)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think about what happens with small numbers. If the starting number is 1, the first player loses immediately.
If the starting number is even, the first player can always win. They pick a factor that makes the remaining number odd. The second player is then forced to pick an odd number, resulting in an even number after subtraction. This repeats, always giving the first player an even number to work with until the second player is left with the number 1.
If the starting number is odd, the first player can only pick odd factors, leaving an even number for the second player. Now the second player is in the same winning position as the first player was with an even number. The second player can then force the first player to eventually be left with 1.
Therefore, if the starting number is even, the first player wins. If it is odd, the first player loses.

Code Implementation

def divisor_game(number):
    # If the starting number is even, Alice wins.
    if number % 2 == 0:
        return True

    # If the number is 1, Alice loses

    # If the starting number is odd, Alice loses.
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 1	Alice loses immediately as there are no divisors x such that 0 < x < 1, so return false.
n = 2	Alice chooses x = 1, n becomes 1, Bob loses; therefore, Alice wins so return true.
Large values of n	Memoization or dynamic programming is necessary to avoid exponential time complexity from repeated calculations for the same n.
n is a prime number	Alice can only choose 1, reducing n to n-1, and the game continues depending on n-1.
n is a power of 2	This can influence the win/loss pattern; the solution should correctly determine the outcome through the game's rules.
Recursion depth exceeding limits without memoization	If the approach is recursive, ensure memoization is used to prevent stack overflow errors for large values of n.
Integer overflow when calculating n - x	The problem statement guarantees n is an integer so integer overflow is not a concern for subtraction given that x < n.
Time Limit Exceeded (TLE) for large n without optimization	Ensure the solution uses efficient algorithms like dynamic programming or memoization to reduce time complexity.