Find the winner of a game of donating i candies in every i-th move

Find the winner of a game of donating i candies in every i-th move

Given two integers X and Y representing the number of candies allocated to players A and B respectively, where both the players indulge in a game of donating i candies to the opponent in every i^th move. Starting with player A, the game continues with alternate turns until a player is unable to donate the required amount of candies and loses the game, the task is to find the winner of the game.

Examples:

Input: X = 2, Y = 3
Output: A
Explanation: The game turns out in the following manner:

X

0

2

3

1

1

4

2

3

2

3

0

5

4

4

1

Step		Y

Since A fails to donate 5 candies in the 5^th step, B wins the game.

 Input: X = 2, Y = 1
Output: B
Explanation: The game turns out in the following manner:

Step	X	Y
0	2	1
1	1	2
2	3	0
3	0	3

Since B fails to give 4 candies in the 4^th step, A wins the game.

Approach: The idea is to solve the problem based on the following observation:

Number of candies
Possessed by A

Number of candies
Possessed by B

0

X

Y

1

X – 1

Y + 1

2

X – 1 + 2 = X + 1

Y + 1 – 2 = Y – 1

3

X – 2

Y + 2

4

X + 2

Y – 2

Step

• The player whose candies reduce to 0 first, will not be having enough candies to give in the next move.
• Count of candies of player A decreases by 1 in odd moves.
• Count of candies of player B decreases by 1 in even moves.

Follow the steps below to solve the problem:

1. Initialize two variables, say chanceA and chanceB, representing the number of moves in which the number of candies possessed by a player reduces to 0.
2. Since count of candies of player A decreases by 1 in odd moves, chanceA = 2 * (X – 1) + 1
3. Since count of candies of player B decreases by 1 in even moves, chanceB = 2 * Y
4. If chanceA < chanceB, then B will be the winning player.
5. Otherwise, A will be the winning player.
6. Print the winning player.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int stepscount(int a, int b) {               int chanceA = 2 * a - 1;                  int chanceB = 2 * b;             if (chanceA < chanceB) {         cout << "B";     }             else if (chanceB < chanceA) {         cout << "B";     }        return 0; }    int main() {                       int A = 2;                  int B = 3;        stepscount(A, B);        return 0; }

Time Complexity: O(1)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets