Last Updated: 27 Jun, 2021
Winner Of Candies
Easy
You and your friend met after a long time and decided to have candies. You brought ‘X’ candies while your friend brought ‘Y’ candies. Since you both were bored you decided to play a game where each of you will play one by one and you will start first. The game goes as follows :
In the ith move, the person will give i candies to the other person.
The person who is unable to donate the required amount of candies will lose. You are required to find out who will win the game.
For Example:
For X = 1, Y = 2 the game goes as follows -
You will donate 1 candy. So you now have 0 and your friend has 3 candies.
Your friend will donate 2 candies. So you now have 2 and your friend has 1 candy.
You are required to donate 3 candies but you only have 2 candies.
Hence your friend wins.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers X and Y which denote the number of candies you and your friend have initially.
Output Format:
For each test case, print “Win” if you will win the game and “Lose” if you don’t win the game.
Output for each test case will be printed in a separate line.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= X, Y <= 10^9
Time Limit: 1 sec.
Approaches
Try to start from move 1 and in each move update the number of candies with you and your friend respectively. As soon as one of you has less than 0 candies declare the other one as the winner.
Algorithm:
winnerOfCandies (X, Y) returns whether the first player wins or loses.
- Start an infinite loop which is the game and an integer variable i which denotes the move number currently.
- If i is odd it means it is your turn hence decrease ‘X’ by ‘i’ and increase ‘Y’ by ‘i’.
- Else it is your friend’s turn. Decrease the value of ‘Y’ by ‘i’ and increase ‘X’ by ‘i’.
- As soon as one of them becomes < 0 return Win if it is ‘Y’ else return ‘X’
- increase ‘i’ by ‘1’.
The values of X and Y at the first few turns of the games are as follows -
| Turn No. | X | Y |
| 0 | X | Y |
| 1 | X - 1 | Y + 1 |
| 2 | X + 1 | Y - 1 |
| 3 | X + 1 - 3 = X - 2 | Y - 1 + 3 = Y + 2 |
| 4 | X -2 + 4 = X + 2 | Y + 2 - 4 = Y - 2 |
You can observe that the value of X decreases by 1 at every odd turn and that of Y decreases by 1 at every even turn.
So the value of X becomes zero at exactly 2*X - 1 turns and the value of Y becomes zero at exactly 2*Y turn. So we calculate which one becomes zero first and output the other one as the winner
Algorithm:
winnerOfCandies (X, Y) returns whether the first player wins or loses.
- Calculate ‘TurnA’ = 2 * ‘X’ - 1.
- Calculate the ‘TurnB’ = 2 * ‘Y’ - 1
- if ‘TurnA’ < ‘TurnB’ return “Lose”
- else return “Win”