Find the winner of game where X picks 1, then Y picks 2, then X picks 3 and so on
Two players X and Y are picking up numbers alternatively with X picking first. In the first turn X picks 1, then Y picks 2, then X picks 3 and the game goes on like this. When a player cannot pick a number he loses the game. Given 2 integers A and B denoting the maximum sum of the numbers X and Y can pick respectively. Find the winner of the game.
Examples:
Input: A = 3, B = 2
Output: Y
Explanation: Initially, X picks 1, Y picks 2.
Now in third move X can only pick 3, thereby making the sum (1+3) = 4.
4 exceed total permissible sum for X i.e. 3. So the winner is YInput: A = 4, B = 2
Output: X
Approach: The task can be solved by maintaining 2 sums, one for X and one for Y. Follow the below steps to solve the problem:
- The maximum limit of X and Y is A and B respectively.
- Initialize the total sum for X and Y with 0.
- Initialize counter with 0.
- Run while loop until (total_x ≤ A and total_y ≤ B)
- Increment counter
- After loop break, check who crossed the limit first
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 winner void winner( int A, int B) { // Initialize with zero int total_x, total_y, counter = 0; // Fixed limit while (total_x <= A && total_y <= B) { // Increment counter counter = counter + 1; // X's total total_x = total_x + counter; // Increment counter counter = counter + 1; // Y's total total_y = total_y + counter; } if (total_x > A && total_y > B) cout << "Y" ; else if (total_x > A) cout << "Y" ; else cout << "X" ; } // Driver Code int main() { int A = 3, B = 2; winner(A, B); return 0; } |
C
// C program for the above approach #include <stdio.h> // Function to find the winner void winner( int A, int B) { // Initialize with zero int total_x, total_y, counter = 0; // Fixed limit while (total_x <= A && total_y <= B) { // Increment counter counter = counter + 1; // X's total total_x = total_x + counter; // Increment counter counter = counter + 1; // Y's total total_y = total_y + counter; } if (total_x > A && total_y > B) printf ( "Y" ); else if (total_x > A) printf ( "Y" ); else printf ( "X" ); } // Driver Code void main() { int A = 3, B = 2; winner(A, B); } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the winner static void winner( int A, int B) { // Initialize with zero int total_x = 0 , total_y = 0 , counter = 0 ; // Fixed limit while (total_x <= A && total_y <= B) { // Increment counter counter = counter + 1 ; // X's total total_x = total_x + counter; // Increment counter counter = counter + 1 ; // Y's total total_y = total_y + counter; } if (total_x > A && total_y > B) System.out.println( "Y" ); else if (total_x > A) System.out.println( "Y" ); else System.out.println( "X" ); } // Driver Code public static void main (String[] args) { int A = 3 , B = 2 ; winner(A, B); } } // This code is contributed by hrithikgarg03188. |
Python
# Python program for the above approach # Function to find the winner def winner(A, B): # Initialize with zero total_x = 0 total_y = 0 counter = 0 # Fixed limit while (total_x < = A and total_y < = B): # Increment counter counter = counter + 1 # X's total total_x = total_x + counter # Increment counter counter = counter + 1 # Y's total total_y = total_y + counter if (total_x > A and total_y > B): print ( "Y" ) elif (total_x > A): print ( "Y" ) else : print ( "X" ) # Driver Code A = 3 B = 2 winner(A, B) # This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approach using System; class GFG { // Function to find the winner static void winner( int A, int B) { // Initialize with zero int total_x = 0, total_y = 0, counter = 0; // Fixed limit while (total_x <= A && total_y <= B) { // Increment counter counter = counter + 1; // X's total total_x = total_x + counter; // Increment counter counter = counter + 1; // Y's total total_y = total_y + counter; } if (total_x > A && total_y > B) Console.WriteLine( "Y" ); else if (total_x > A) Console.WriteLine( "Y" ); else Console.WriteLine( "X" ); } // Driver Code public static void Main () { int A = 3, B = 2; winner(A, B); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the winner function winner(A, B) { // Initialize with zero let total_x, total_y, counter = 0; // Fixed limit while (total_x <= A && total_y <= B) { // Increment counter counter = counter + 1; // X's total total_x = total_x + counter; // Increment counter counter = counter + 1; // Y's total total_y = total_y + counter; } if (total_x > A && total_y > B) document.write( "Y" ) else if (total_x > A) document.write( "Y" ) else document.write( "X" ) } // Driver Code let A = 3, B = 2; winner(A, B); // This code is contributed by Potta Lokesh </script> |
Y
Time Complexity: O(A+B)
Auxiliary Space: O(1)
Another Approach:
- Start by initializing the maximum limit for X and Y as A and B respectively.
- Initialize the total sum for X and Y as 0.
- Initialize a boolean flag x_wins as true.
- Use a for loop to iterate over the numbers X and Y pick.
- In each iteration, add the current number to the total sum for X and Y.
- If the total sum for X exceeds A, set x_wins to false and break the loop.
- If the total sum for Y exceeds B, set x_wins to true and break the loop.
- After the loop, check the value of x_wins. If it is true, X wins, else Y wins.
- Print the winner of the game.
Below is the implementation of above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the winner void winner( int A, int B) { // Initialize with zero int total_x = 0, total_y = 0; bool x_wins = true ; // Iterate over the numbers X and Y pick for ( int i = 1; total_x <= A && total_y <= B; i += 2) { total_x += i; if (total_x > A) { x_wins = false ; break ; } total_y += i+1; if (total_y > B) { x_wins = true ; break ; } } if (x_wins) cout << "X" ; else cout << "Y" ; } // Driver Code int main() { int A = 3, B = 2; winner(A, B); return 0; } |
Java
public class GameWinner { public static void winner( int A, int B) { int total_x = 0 , total_y = 0 ; boolean x_wins = true ; for ( int i = 1 ; total_x <= A && total_y <= B; i += 2 ) { total_x += i; if (total_x > A) { x_wins = false ; break ; } total_y += i+ 1 ; if (total_y > B) { x_wins = true ; break ; } } if (x_wins) System.out.println( "X" ); else System.out.println( "Y" ); } public static void main(String[] args) { int A = 3 , B = 2 ; winner(A, B); } } |
Python3
def winner(A, B): total_x = 0 total_y = 0 x_wins = True for i in range ( 1 , A + B + 1 , 2 ): total_x + = i if total_x > A: x_wins = False break total_y + = i + 1 if total_y > B: x_wins = True break if x_wins: print ( "X" ) else : print ( "Y" ) A = 3 B = 2 winner(A, B) |
C#
using System; public class GameWinner { public static void winner( int A, int B) { int total_x = 0, total_y = 0; bool x_wins = true ; for ( int i = 1; total_x <= A && total_y <= B; i += 2) { total_x += i; if (total_x > A) { x_wins = false ; break ; } total_y += i+1; if (total_y > B) { x_wins = true ; break ; } } if (x_wins) Console.WriteLine( "X" ); else Console.WriteLine( "Y" ); } public static void Main() { int A = 3, B = 2; winner(A, B); } } |
Javascript
function winner(A, B) { let total_x = 0; let total_y = 0; let x_wins = true ; for (let i = 1; total_x <= A && total_y <= B; i += 2) { total_x += i; if (total_x > A) { x_wins = false ; break ; } total_y += i+1; if (total_y > B) { x_wins = true ; break ; } } if (x_wins) console.log( "X" ); else console.log( "Y" ); } let A = 3; let B = 2; winner(A, B); |
Y
Time Complexity: O(A+B)
Auxiliary Space: O(1)
Approach: Using Dynamic Programming
Steps:
- First, the find_winner function takes two integers A and B as input and returns the winner of the game.
- Using a 2D vector memo to memoize the states and their winners.
- The function f takes two integers i and j as input and returns the winner of the game starting from the state (i, j).
- check if the state has already been memoized and return the result if it has.
- If i <= 0, then the game is over and the other player wins. Similarly, if j <= 0, then the current player wins.
- Otherwise, we iterate over all the numbers from 1 to min(i, j).
- check if the other player can win starting from the next state.
- If the other player can win from at least one of the next states, then the current player can win from the current state, and vice versa.
- Last memoize the result and return it.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Returns the winner of the game // given the maximum sums X and Y can pick char find_winner( int A, int B) { // Initialize a 2D vector vector<vector< char > > memo(A + 1, vector< char >(B + 1, ' ' )); // Recursive function to calculate the winner function< char ( int , int )> f = [&]( int i, int j) { if (memo[i][j] != ' ' ) { return memo[i][j]; } if (i <= 0) { memo[i][j] = 'Y' ; } else if (j <= 0) { memo[i][j] = 'X' ; } else { bool can_win = false ; for ( int num = 1; num <= min(i, j); num++) { if (f(i - num, j) == 'Y' ) { can_win = true ; break ; } } memo[i][j] = can_win ? 'X' : 'Y' ; } return memo[i][j]; }; return f(A, B); } // Driver Code int main() { int A = 3, B = 2; cout << find_winner(A, B) << endl; return 0; } |
Java
import java.util.Arrays; public class GFG { // Returns the winner of the game given the maximum sums X and Y can pick static char findWinner( int A, int B) { // Initialize a 2D array char [][] memo = new char [A + 1 ][B + 1 ]; for ( char [] row : memo) { Arrays.fill(row, ' ' ); } // Recursive function to calculate the winner return f(A, B, memo); } static char f( int i, int j, char [][] memo) { if (memo[i][j] != ' ' ) { return memo[i][j]; } if (i <= 0 ) { memo[i][j] = 'Y' ; } else if (j <= 0 ) { memo[i][j] = 'X' ; } else { boolean canWin = false ; for ( int num = 1 ; num <= Math.min(i, j); num++) { if (f(i - num, j, memo) == 'Y' ) { canWin = true ; break ; } } memo[i][j] = canWin ? 'X' : 'Y' ; } return memo[i][j]; } // Driver Code public static void main(String[] args) { int A = 3 , B = 2 ; System.out.println(findWinner(A, B)); } } |
Python3
def find_winner(A, B): # Initialize a 2D list memo = [[ ' ' for _ in range (B + 1 )] for _ in range (A + 1 )] # Recursive function to calculate the winner def f(i, j): if memo[i][j] ! = ' ' : return memo[i][j] if i < = 0 : memo[i][j] = 'Y' elif j < = 0 : memo[i][j] = 'X' else : can_win = False for num in range ( 1 , min (i, j) + 1 ): if f(i - num, j) = = 'Y' : can_win = True break memo[i][j] = 'X' if can_win else 'Y' return memo[i][j] return f(A, B) # Driver Code A, B = 3 , 2 print (find_winner(A, B)) # code is contributed by shinjanpatra |
C#
using System; class Program { // Returns the winner of the game given the maximum sums X and Y can pick static char FindWinner( int A, int B) { // Initialize a 2D array char [,] memo = new char [A + 1, B + 1]; // Recursive function to calculate the winner Func< int , int , char > f = null ; f = (i, j) => { if (memo[i, j] != '\0' ) { return memo[i, j]; } if (i <= 0) { memo[i, j] = 'Y' ; } else if (j <= 0) { memo[i, j] = 'X' ; } else { bool canWin = false ; for ( int num = 1; num <= Math.Min(i, j); num++) { if (f(i - num, j) == 'Y' ) { canWin = true ; break ; } } memo[i, j] = canWin ? 'X' : 'Y' ; } return memo[i, j]; }; return f(A, B); } // Driver Code static void Main( string [] args) { int A = 3, B = 2; Console.WriteLine(FindWinner(A, B)); } } |
Javascript
<script> function findWinner(A, B) { // Initialize a 2D array const memo = new Array(A + 1); for (let i = 0; i <= A; i++) { memo[i] = new Array(B + 1).fill( ' ' ); } // Recursive function to calculate the winner function f(i, j) { if (memo[i][j] !== ' ' ) { return memo[i][j]; } if (i <= 0) { memo[i][j] = 'Y' ; } else if (j <= 0) { memo[i][j] = 'X' ; } else { let canWin = false ; for (let num = 1; num <= Math.min(i, j); num++) { if (f(i - num, j) === 'Y' ) { canWin = true ; break ; } } memo[i][j] = canWin ? 'X' : 'Y' ; } return memo[i][j]; } return f(A, B); } // Driver Code const A = 3; const B = 2; console.log(findWinner(A, B)); </script> // code is contributed by shinjanpatra |
Y
Time Complexity: O(AB)
Auxiliary Space: O(AB)