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 ith 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:
Step
X
Y
0
2
3
1
1
4
2
3
2
3
0
5
4
4
1
Since A fails to donate 5 candies in the 5th 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 4th step, A wins the game.
Approach: The idea is to solve the problem based on the following observation:
Step
Number of candies
Possessed by ANumber of candies
Possessed by B0
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
- 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:
- 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.
- Since count of candies of player A decreases by 1 in odd moves, chanceA = 2 * (X – 1) + 1
- Since count of candies of player B decreases by 1 in even moves, chanceB = 2 * Y
- If chanceA < chanceB, then B will be the winning player.
- Otherwise, A will be the winning player.
- Print the winning player.
Below is the implementation of the above approach:
C++
// C++ Program for the// above approach#include <bits/stdc++.h>using namespace std;// Function to find the winning// player in a game of donating i// candies to opponent in i-th moveint stepscount(int a, int b){ // Steps in which number of // candies of player A finishes int chanceA = 2 * a - 1; // Steps in which number of // candies of player B finishes int chanceB = 2 * b; // If A's candies finishes first if (chanceA < chanceB) { cout << "B"; } // Otherwise else if (chanceB < chanceA) { cout << "A"; } return 0;}// Driver Codeint main(){ // Input // Candies possessed // by player A int A = 2; // Candies possessed // by player B int B = 3; stepscount(A, B); return 0;} |
Java
// Java Program for above approachclass GFG{ // Function to find the winning// player in a game of donating i// candies to opponent in i-th movestatic void stepscount(int a, int b){ // Steps in which number of // candies of player A finishes int chanceA = 2 * a - 1; // Steps in which number of // candies of player B finishes int chanceB = 2 * b; // If A's candies finishes first if (chanceA < chanceB) { System.out.print("B"); } // Otherwise else if (chanceB < chanceA) { System.out.print("A"); }}// Driver codepublic static void main(String[] args){ // Input // Candies possessed by player A int A = 2; // Candies possessed by player B int B = 3; stepscount(A, B);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to find the winning# player in a game of donating i# candies to opponent in i-th movedef stepscount(a, b): # Steps in which number of # candies of player A finishes chance_A = 2 * a - 1 # Steps in which number of # candies of player B finishes chance_B = 2 * b # If A's candies finishes first if (chance_A < chance_B): return 'B' # Otherwise else: return "A"# Driver code# Candies possessed by player A A = 2# Candies possessed by player BB = 3print(stepscount(A, B))# This code is contributed by abhinavjain194 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the winning// player in a game of donating i// candies to opponent in i-th movestatic void stepscount(int a, int b){ // Steps in which number of // candies of player A finishes int chanceA = 2 * a - 1; // Steps in which number of // candies of player B finishes int chanceB = 2 * b; // If A's candies finishes first if (chanceA < chanceB) { Console.Write("B"); } // Otherwise else if (chanceB < chanceA) { Console.Write("A"); }}// Driver codestatic void Main(){ // Input // Candies possessed by player A int A = 2; // Candies possessed by player B int B = 3; stepscount(A, B);}}// This code is contributed by abhinavjain194 |
Javascript
<script>// Javascript program for the above approach// Function to find the winning// player in a game of donating i// candies to opponent in i-th movefunction stepscount( a, b){ // Steps in which number of // candies of player A finishes let chanceA = 2 * a - 1; // Steps in which number of // candies of player B finishes ;let chanceB = 2 * b; // If A's candies finishes first if (chanceA < chanceB) { document.write("B"); } // Otherwise else if (chanceB < chanceA) { document.write("A"); } return 0;}// Driver Code// Input// Candies possessed// by player Alet A = 2;// Candies possessed// by player Blet B = 3;stepscount(A, B);</script> |
Output:
B
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
