Given an arr[] of positive integers of length N. Player X and Y plays a game where in each move one person chooses two elements of arr[] (say arr[i] and arr[j]) such that 0 ? i < j ? N – 1 and arri should be greater than 0 and Then decrement arri and increment arrj. When one player is unable to make such a move the player loses. The task is to find the winner of the game if Y starts the game.
Examples:
Input: N = 4, arr[] = {2, 3, 1, 3}
Output: Y
Explanation: initial arr[] is: {2, 3, 1, 3}
Player Y applied by selecting i = 0 and j = 1: {1, 4, 1, 3}
Player X applied by selecting i = 0 and j = 1: {0, 5, 1, 3}
Player Y applied by selecting i = 1 and j = 2: {0, 4, 2, 3}
Player X applied by selecting i = 1 and j = 2: {0, 3, 3, 3}
Player Y applied by selecting i = 1 and j = 2: {0, 2, 4, 3}
Player X applied by selecting i = 1 and j = 2: {0, 1, 5, 3}
Player Y applied by selecting i = 1 and j = 2: {0, 0, 6, 3}
Player X applied by selecting i = 2 and j = 3: {0, 0, 5, 4}
Player Y applied by selecting i = 2 and j = 3: {0, 0, 4, 5}
Player X applied by selecting i = 2 and j = 3: {0, 0, 3, 6}
Player Y applied by selecting i = 2 and j = 3: {0, 0, 2, 7}
Player X applied by selecting i = 2 and j = 3: {0, 0, 1, 8}
Player Y applied by selecting i = 2 and j = 3: {0, 0, 0, 9}
As there are no more indices i and j left in arr[],
Which follows 0<=i<j<N-1 and Ai > 0.
Therefore, player X can’t make its next operation.
Therefore, Player Y wins the game.Input: N = 2, arr[] = {0, 1}
Output: X
Explanation: Player Y can’t make very first operation of the game, Therefore player X wins the game.
Approach: To solve the problem follow the below idea:
As we can see that it is clearly mentioned in the game that index i (0 ? i ? N – 1) should be greater than index j for applying operation, Thus by this observation, we can see that at any index i in input arr[] there are N – i – 1 possibles positions for subtracting one from ith index and add it to jth index. Thus the game reduced into sub-games and is similar like “Game of Nim”.
- In Game of Nim, Winner decides on the basis of Nim-Sum. If Nim-sum is not equal to zero then player who makes first move wins and if Nim-Sum is equal to zero then other player Wins.
- Same this problem is related to Combinatorial Game Theory and uses Sprague Grundy Theorem to solve the problem.
- Game of Nim depends upon only Nim-sum and we have a XOR property as (A^A) = 0.If an element is even at index i, then it will give its part as even N-i in overall Nim-sum else odd N-i in overall Nim-sum.
According to above three lines, we can conclude that to get the answer calculate XOR of N-i-1 with the ith element, where ith element is odd in arr[].
if Nim-Sum comes zero then player X wins else player Y wins.
Follow the steps to solve the problem:
- Create any long type variable let’s say Z and initialize it to 0.
- Iterate on arr[] from left to right, if an element is found odd, Then update Z as Z ? (N – i – 1).
- After completing iteration if Z = 0, Then player X wins else Y wins.
- Print X/Y as the winner based on the resultant value of Z in the above step.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;void find_winner(int N, int arr[]){ long Z = 0; // Loop for iterating on arr[] for (int i = 0; i < N; i++) { // Checking current iterated // element is odd or not if (arr[i] % 2 == 1) { // Updating value of Z if // odd element found Z = Z ^ (N - i - 1); } } // Printing winner by using // value of Z if (Z == 0) { cout<<"X"; } else { cout<<"Y"; }}// Function which is called in mainint main() { // Driver function // Input N which denotes number of // positive elements in arr[] int N = 4; // Input arr[] int arr[] = { 2, 3, 1, 3 }; // Function call find_winner(N, arr); return 0;}// This code is contributed by satwik4409. |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Driver function public static void main(String[] args) { // Input N which denotes number of // positive elements in arr[] int N = 4; // Input arr[] int[] arr = { 2, 3, 1, 3 }; // Function call find_winner(N, arr); } // Function which is called in main static void find_winner(int N, int[] arr) { long Z = 0; // Loop for iterating on arr[] for (int i = 0; i < N; i++) { // Checking current iterated // element is odd or not if (arr[i] % 2 == 1) { // Updating value of Z if // odd element found Z = Z ^ (N - i - 1); } } // Printing winner by using // value of Z if (Z == 0) { System.out.println("X"); } else { System.out.println("Y"); } }} |
Python3
# Python3 code to implement the approachdef find_winner(N, arr) : Z = 0 # Loop for iterating on arr[] for i in range(N): # Checking current iterated # element is odd or not if (arr[i] % 2 == 1) : # Updating value of Z if # odd element found Z = Z ^ (N - i - 1) # Printing winner by using # value of Z if (Z == 0) : print("X") else : print("Y") # Function which is called in mainif __name__ == "__main__": # Driver function # Input N which denotes number of # positive elements in arr[] N = 4 # Input arr[] arr = [ 2, 3, 1, 3 ] # Function call find_winner(N, arr) # This code is contributed by sanjoy_62. |
C#
// C# code to implement the approachusing System;public class GFG { // Function which is called in main static void find_winner(int N, int[] arr) { long Z = 0; // Loop for iterating on arr[] for (int i = 0; i < N; i++) { // Checking current iterated // element is odd or not if (arr[i] % 2 == 1) { // Updating value of Z if // odd element found Z = Z ^ (N - i - 1); } } // Printing winner by using // value of Z if (Z == 0) { Console.WriteLine("X"); } else { Console.WriteLine("Y"); } } static public void Main() { // Input N which denotes number of // positive elements in arr[] int N = 4; // Input arr[] int[] arr = { 2, 3, 1, 3 }; // Function call find_winner(N, arr); }}// This code is contributed by Rohit Pradhan |
Javascript
//javascript code to implement the approachfunction find_winner( N, arr){ let Z = 0; // Loop for iterating on arr[] for (let i = 0; i < N; i++) { // Checking current iterated // element is odd or not if (arr[i] % 2 == 1) { // Updating value of Z if // odd element found Z = Z ^ (N - i - 1); } } // Printing winner by using // value of Z if (Z == 0) { console.log("X"); } else { console.log("Y"); }}// Function which is called in main // Driver function // Input N which denotes number of // positive elements in arr[] let N = 4; // Input arr[] let arr = [ 2, 3, 1, 3 ]; // Function call find_winner(N, arr); //this code is contributed by ksam24000 |
Y
Time Complexity: O(N)
Auxiliary Space: O(1)
