Winner Of Candies

Easy
0/40
Average time to solve is 20m
5 upvotes

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
3 2
Sample Output 1:
Win
Explanation For Sample Output 1:
The game proceeds as follows:-

link

Sample Input 2:
1
100 1
Sample Output 2:
Win
Hint

Can you simulate each and every move of the game?

Approaches (2)
Brute Force

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.

  1. Start an infinite loop which is the game and an integer variable i which denotes the move number currently.
  2. If i is odd it means it is your turn hence decrease ‘X’ by ‘i’ and increase ‘Y’ by ‘i’.
  3. Else it is your friend’s turn. Decrease the value of ‘Y’ by ‘i’ and increase ‘X’ by ‘i’.
  4. As soon as one of them becomes < 0 return Win if it is ‘Y’ else return ‘X’
  5. increase ‘i’ by ‘1’.
Time Complexity

O(max(X, Y)), Where ‘X’ and ‘Y’ are the initial number of candies with both of you.

Since at every turn the value of either X or Y decreases, the game will end in 2 * max(X, Y) turns.

 

Space Complexity

O(1)

 

Constant space is used.

Code Solution
(100% EXP penalty)
Winner Of Candies
Full screen
Console