Given the number of small and large balls N and M respectively, the task is to find which player wins if both the player X and Y play optimally by making the following two moves:
- Player X will try to keep the same type of ball i.e., small followed by another small ball or large ball is followed by a large ball.
- Player Y will put different types of ball i.e., small followed by a large ball or vice-versa.
The player who cannot make a move loses the game. The task is to find which player won the game the given number of balls. It is given that player X always starts first.
Examples:
Input: N = 3 M = 1
Output: X
Explanation:
Since there is only 1 large ball, player X will puts it first.
Player Y puts a small ball adjacent to large one, because he can put a different type of ball adjacently.
Then player X puts a small ball (same type). Now player Y can’t keep a ball and hence cannot make a move
Sequence = {large, small, small}, hence the score would X = 2 and Y = 1.
Hence, player X wins.Input: N = 4 M = 4
Output: Y
Explanation:
Player X first move = small, Player Y first move = large ( N = 4, M = 3 )
Player X second move = large, Player Y second move = small ( N = 3, M = 2 )
Player X third move = small, Player Y third move = large ( N = 2, M = 1 )
Player X fourth move = large, Player Y fourth move = small ( N = 1, M = 0 ).
Hence, player Y wins as player X can’t make a move.
Approach: Follow the steps given below to solve the problem:
- Check if the number of small balls is greater than or equals the number of large balls, then player X will have the score N – 1 since the player X will place small ball first then player Y will immediately put a different type of ball and now player X will put the same as player Y type’s ball. This process will continue until the end of the game.
- Otherwise, if the large balls are greater than small balls then player X will have M – 1 score and player Y will have a score as N, the approach will be the same as mentioned above. Here the player X will first start by keeping large ball first.
- In the end, compare the scores of both the players and print the winner as output.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find the winner of the// Game by arranging the balls in a rowvoid findWinner(int n, int m){ int X = 0; int Y = 0; // Check if small balls are greater // or equal to the large ones if (n >= m) { // X can place balls // therefore scores n-1 X = n - 1; Y = m; } // Condition if large balls // are greater than small else { // X can have m-1 as a score // since greater number of // balls can only be adjacent X = m - 1; Y = n; } // Compare the score if (X > Y) cout << "X"; else if (Y > X) cout << "Y"; else cout << "-1";}// Driver Codeint main(){ // Given number of small balls(N) // and number of large balls(M) int n = 3, m = 1; // Function call findWinner(n, m); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find the winner of the// Game by arranging the balls in a rowstatic void findWinner(int n, int m){ int X = 0; int Y = 0; // Check if small balls are greater // or equal to the large ones if (n >= m) { // X can place balls // therefore scores n-1 X = n - 1; Y = m; } // Condition if large balls // are greater than small else { // X can have m-1 as a score // since greater number of // balls can only be adjacent X = m - 1; Y = n; } // Compare the score if (X > Y) System.out.print("X"); else if (Y > X) System.out.print("Y"); else System.out.print("-1");} // Driver Codepublic static void main(String[] args){ // Given number of small balls(N) // and number of large balls(M) int n = 3, m = 1; // Function call findWinner(n, m);}}// This code is contributed by rock_cool |
Python3
# Python3 program for the above approach# Function to find the winner of the# Game by arranging the balls in a rowdef findWinner(n, m): X = 0; Y = 0; # Check if small balls are greater # or equal to the large ones if (n >= m): # X can place balls # therefore scores n-1 X = n - 1; Y = m; # Condition if large balls # are greater than small else: # X can have m-1 as a score # since greater number of # balls can only be adjacent X = m - 1; Y = n; # Compare the score if (X > Y): print("X"); elif(Y > X): print("Y"); else: print("-1");# Driver Codeif __name__ == '__main__': # Given number of small balls(N) # and number of large balls(M) n = 3; m = 1; # Function call findWinner(n, m);# This code is contributed by Rohit_ranjan |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the winner of the// Game by arranging the balls in a rowstatic void findWinner(int n, int m){ int X = 0; int Y = 0; // Check if small balls are greater // or equal to the large ones if (n >= m) { // X can place balls // therefore scores n-1 X = n - 1; Y = m; } // Condition if large balls // are greater than small else { // X can have m-1 as a score // since greater number of // balls can only be adjacent X = m - 1; Y = n; } // Compare the score if (X > Y) Console.Write("X"); else if (Y > X) Console.Write("Y"); else Console.Write("-1");} // Driver Codepublic static void Main(String[] args){ // Given number of small balls(N) // and number of large balls(M) int n = 3, m = 1; // Function call findWinner(n, m);}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program for the above approach// Function to find the winner of the// Game by arranging the balls in a rowfunction findWinner(n, m){ let X = 0; let Y = 0; // Check if small balls are greater // or equal to the large ones if (n >= m) { // X can place balls // therefore scores n-1 X = n - 1; Y = m; } // Condition if large balls // are greater than small else { // X can have m-1 as a score // since greater number of // balls can only be adjacent X = m - 1; Y = n; } // Compare the score if (X > Y) document.write("X"); else if (Y > X) document.write("Y"); else document.write("-1");}// Driver code// Given number of small balls(N)// and number of large balls(M)let n = 3, m = 1;// Function callfindWinner(n, m);// This code is contributed by divyesh072019</script> |
Output:
X
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!