Solution
Approach 1: Dynamic Programming
Let dp[i] indicate the result of the game for the given number i. dp[i] = true if the player wins, otherwise false. For any number i, traverse from j=1 to j=i-1. If j is a factor of i then j can be subtracted from i as per the rules. If dp[i-j] is false then it means Alice will choose j as then Bob will get i-j and he will lose.
Base case: dp[0] = false, dp[1] = false
Java code:
public boolean divisorGame(int N) {
boolean[] dp = new boolean[N+1];
dp[0] = false;
dp[1] = false;
for(int i=2; i <= N; i++){
for(int j=1; j < i; j++){
if(i % j == 0){
if(dp[i-j] == false){
dp[i] = true;
break;
}
}
}
}
return dp[N];
}
Time complexity: O(N^2)
Approach 2: Math
Base case: For N=1, Alice loses. For N=2, Alice wins.
Now, odd numbers only have odd factors (if number is prime, the factors will be 1 and the number itself but we don’t consider the number itself as per the rules of the question). Thus, subtracting any factor from an odd number gives us an even number.
Now, if Alice gets an even number, she will subtract 1 and give an odd number to Bob. Now, Bob has an odd number so he always returns an even number to Alice no matter what he subtracts. This way, Alice ends up with the smallest even number as per the rules, that is, 2 and wins.
When Alice gets an odd number, she can only pass on an even number to Bob. So now Bob will apply the above strategy and always subtract 1 from the even number to return an odd number back to Alice. Until Bob receives 2 which is when he wins!
So Alice can only win the game when she receives an even number given that both players play optimally.
bool divisorGame(int N) {
return N%2==0;
}
Time complexity: O(1)