Adobe Interview Question
Software Engineer / DevelopersThe trick is to see that who ever gets to N-5 wins. So the strategy is reduces to getting to N-5. But then whoever gets to N-10 wins, etc. It, then is easy to see that whoever can get to N-5k where k is the largest number s.t. N-5k is positive, will win. That could be either player depending on the number.
the strategy says that to be in a winning situation you must put the opponent in a
position where the remaining points to reach the score value N is divisible by 5(considering that we are allowed to choose only 1,2,3,4)and he/she has to choose.
Suppose, the remaining points to reach the score is x.
Then, if (x%5)=4 on your turn , choose 4
if (x%5)=3 on your turn , choose 3
if (x%5)=2 on your turn , choose 2
if (x%5)=1 on your turn , choose 1
if (x%5)=0 on your turn , you may not win if the opponent is smart enough
and follows the above strategy
if the question says the no one player will chose can not be chosen by other immediately for e.g. if player A has chosen 4 then player B cant choose 4 right at this moment then the no to be choose is = no/4;no = no - no/4;
else the question is trivial...the first person will win always..
Following will be my strategy,
- Patron May 21, 2010a) if difference between N and current score is greater than 8. I will choose 4
b) if difference between N and current score is less than 9 but greater than 4. I will (choose N - current_Score -5 )
c) if difference between N and current score is less than 5, I will choose the number it self.
If this strategy is used by both then person from whom we started will win.