The Divisor Game
Two friends are playing a divisor game where every time a number is reduced by one of its factors. A player loses if they can’t reduce the number any further. Our task is to know which one of the friends will win the game called the divisor game.
Saurabh and Reyansh played a divisor game. Initially, there is a number ‘n’. Each player had to think of a number x where 0 < x < n such that n % x == 0. After each turn number is replaced with n - x. The divisor game ends when a player cannot make a move and he loses.
Saurabh starts first and they both play optimally. Your task is to find if Saurabh would win the game or not. Return True if and only if Saurabh wins the game.
- Suppose n=2
If Saurabh starts first, the optimal choice would be x=1.
The next number would be 2-1 = 1.
Now, Reyansh can’t make a move. Hence Saurabh wins.
- Suppose n=3
Saurabh chooses 1, and then Reyansh chooses 1.
Hence Now the number is 1, So Saurabh can’t make any move. So Saurabh loses this game.
The problem can be addressed in 2 ways. We’ll check out both of them to give ourselves a broader perspective to handle similar problems we may encounter in the future.
Approach:1 Dynamic Programming
It’s a prerequisite to learn that the player who wins always ends up with 2, which he would reduce to 1, leaving his opponent without any further moves. Let us observe the table given below.
2 -> 1
Analysing the table carefully, we deduce that any player who ends up with an even number always has a choice to end up with a 2.
Saurabh starts the divisor game with 8. He has a choice to reduce it to 4, 6, 7 for Reyansh.
He would reduce it to 7, and Reyansh would reduce the number to 6 for Saurabh.
Saurabh then has a choice to reduce the number to 3, 4, or 5. He reduces the number to 3 for Reyansh.
Then Reyansh has no choice but to reduce it to 2 for Saurabh.
Saurabh then reduces the number to 1 and wins the game.
Both our approaches stem from this logic.
Below is the implementation for the Dynamic Programming approach. There would be multiple overlapping subproblems that could be optimally addressed by maintaining a dp dictionary to store the results as we iterate.
Time Complexity:- The worst-case time complexity would be of the order O(N2) since we are making N(N-1)/2 computations.
Space Complexity:- We are using a dictionary to store the results as we proceed. Since the size of the dictionary is the same as the size of the array, therefore the auxiliary space used is of the order O(n).
Approach: 2 Simplified Approach
From the table above, we deduced that a player needs to plan his moves in such a way that he/she must always end up with a 2 to win the game. A player with an even number always has a choice to end up with 2.
A player with an odd number can’t reduce the number to an odd number for the other player. Since if a number is odd, all its factors would also be odd. Therefore the resultant number generated after subtracting the factor from the initial number would always be even.
Odd - Odd = Even
Even - Even = Even
Odd - Even = Odd
And since players play optimally, The player starting the game must start with an even number if he/she definitely wants to win the game.
The code implementation is fairly simple for this method and is given below.
def divisorGame(n: int):
Time Complexity:- There’s no traversal of the array. Therefore, the time complexity is of the order O(1).
Space Complexity:- We aren’t using any extra space. There’s no extra space required. Therefore, the space complexity is of the order O(1).
1). Which of the two approaches is preferable?
Answer: The second approach is definitely a more optimised approach.
2). What’s the retrieval time from a dictionary?
Answer: The searching time in a dictionary is of the order O(1).
The major takeaway from this problem is that many of these apparently complex problems can be handled with basic logic. Product-based company interviews are mostly structured to test this aspect of a candidate.
The problem has been repeatedly asked in many interviews in the past and is a testament to their assessment objectives. It’s important to understand both approaches to better understand the concept of dynamic programming.