Engineer bro!
Wed Nov 17 2021 (1 year ago)
Engineer by mistake!
I am a software engineer by passion
In this article, you'll learn that how can you use DP to reduce the execution time.
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 $$XX$$ with $$0<X<n0\; <\; X\; <\; n$$ and $$n\mathrm{\%}X==0n\; \backslash \%\; 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.
Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
$$1<=n<=10001\; <=\; n\; <=\; 1000$$
Suppose you have a number $$n=1n=1$$. As per the problem description, Alice will start playing first. For $$n=1n=1$$, there is no x such that ($$0<X<n0\; <\; X\; <\; n$$), hence Alice will lose the game.
Suppose, you have a number $$n=2n=2$$. First, Alice can choose $$X=1X=1$$ and make $$n=1n=1$$. Now, Bob has $$n=1n=1$$ and he can not make any move. So, Bob lose the game.
Suppose, you have a number $$n=4n=4$$. This time Alice can choose either $$11$$ or $$22$$. Now the real DP game begains
.
When you see the above image, then you can see at each level either Alice or Bob is present.
Steps
Alice started the game, now he can choose either 1 or 2
Alice chooses 1
$$n=3n=3$$ and it's Bob's turn. He can choose 1 and n becomes 2
$$n=2n=2$$ and it's Alice's turn. He can choose 1 and n becomes 1
$$n=1n=1$$ and it's Bob's turn. He can not choose any x and Bob loses the game
Alice chooses 2
$$n=2n=2$$ and it's Bob's turn. He can choose 1 and n becomes 1
$$n=1n=1$$ and it's Alice's turn. He can not choose any x, so he loses the game.
You can observe that initially if Alice were not played optimally and choose 2 then Alice would have to lose.
From the above explanation, you can see that at each step you have to make a decision. The decision should be optimal, so the current player wins the game.
You are given a number $$nn$$ and you have to return true
if Alice will win the game or false
.
Alice can win the game if and only if there is a possibility where can Bob loses the game.
Let's $$XX$$ is a set of number which can divide $$nn$$ and $$0<X<n0\; <\; X\; <\; n$$.
Now, $$\mathrm{\forall}\text{\hspace{0.17em}}x\in X\backslash forall\; \backslash thinspace\; x\; \backslash in\; X$$ (for each x of set X), check if Alice is going to win or not
Do the same thing
Implementation
bool wins(int n){
// if a player has 1, then he/she can not make any move
if(n==1)
return false;
// if a player has 2, then he/she can make it 1 and opponent will lose the game
if(n==2)
return true;
for(int i=1; i<n; i++){
// !wins(n-x) -> if opponent will lose the game then current player will win
if(n%i == 0 && !wins(n-x))
return true;
}
return false;
}
At each step, every we are creating $$c(n)c(n)$$ subtrees, where $$c(n)c(n)$$ is the number of divisions of $$nn$$.
So, the time complexity would be exponential.
You can see in the above image, while creating left subtree we are processing $$n=2n=2$$. The same $$n=2n=2$$ is being processed while generating the right subtree.
So, we can remember the previous value of $$wins(2)wins(2)$$ to get rid of calculating it again.
Rest of the explanation can be found in the code
class Solution {
public:
bool divisorGame(int n) {
if(n==1)
return false;
vector<int>wins(n+1,-1);
wins[1] = 0;
wins[2] = 1;
return meWins(n,wins);
}
bool meWins(int n, vector<int>&wins){
// the maximum number which can devide n can be either sqrt(n) or less than sqrt(n)
int sq = ceil(sqrt(n));
for(int i=1; i<=sq; i++){
// if i can not divide n, then don't do anything
if(n%i != 0){
continue;
}
// if the current subtree value is not present into wins, then call the function again
if(wins[n-i] == -1){
meWins(n-i, wins);
continue;
}
// if next player is going to loose, then current is going to win
if(!wins[n-i]){
wins[n-i] = 1;
return true;
}
}
// this player can't not win
wins[n-1] = 0;
return false;
}
};
© 2021 dsabyte. All rights reserved