Given an array arr[] of length, N, the task is to find the winner of a game played by two players A and B optimally, by performing the following operations:
- Player A makes the first move.
- Players need to alternately place + and – sign in front of array elements in their turns.
- After having placed signs in front of all array elements, player A wins if the difference of all the elements is even.
- Otherwise, player B wins.
Examples:
Input: arr[] = {1, 2}
Output: B
Explanation:
All possible ways the game can be played out are:
(+1) – (+2) = -1
(?1) – (+2) = -3
(+1) – (-2) = 3
(-1) – (-2) = 1
Since the differences are odd in all the possibilities, B wins.Input: arr[] = {1, 1, 2}
Output: A
Explanation:
All possible ways the game can be played out are:
(1) – (1) – (2) = -2
(1) – (1) – (-2) = 2
(1) – (-1) – (2) = 0
(1) – (-1) – (-2) = 4
(-1) – (1) – (2) = -4
(-1) – (1) – (-2) = 0
(-1) – (-1) – (2) = -2
(-1) – (-1) – (-2) = 4
Since the differences are even in all the possibilities, A wins.
Naive Approach: The simplest approach is to generate all the possible 2N combinations in which the signs can be placed in the array and check for each combination, check if player A can win or not. If found to be true for any permutation, then print A. Otherwise, player B wins.
Time Complexity: O(2N * N)
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below to optimize the above approach:
- Initialize a variable, say diff, to store the sum of the array elements.
- Traverse the array arr[], over the range of indices [1, N], and update diff by subtracting arr[i] to it.
- If diff % 2 is found to be equal to 0, then print ‘A’. Otherwise, print ‘B’.
Below is the implementation of the above approach:
C++
// C++ program for the// above approach#include <bits/stdc++.h>using namespace std;// Function to check which// player wins the gamevoid checkWinner(int arr[], int N){ // Stores the difference between // +ve and -ve array elements int diff = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update diff diff -= arr[i]; } // Checks if diff is even if (diff % 2 == 0) { cout << "A"; } else { cout << "B"; }}// Driver Codeint main(){ // Given Input int arr[] = { 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call to check // which player wins the game checkWinner(arr, N); return 0;} |
Python3
# Python3 program for the# above approach# Function to check which# player wins the gamedef checkWinner(arr, N): # Stores the difference between # +ve and -ve array elements diff = 0 # Traverse the array for i in range(N): # Update diff diff -= arr[i] # Checks if diff is even if (diff % 2 == 0): print("A") else: print("B")# Driver Codeif __name__ == "__main__": # Given Input arr = [1, 2] N = len(arr) # Function call to check # which player wins the game checkWinner(arr, N) # This code is contributed by ukasp. |
Java
// Java program for the// above approachimport java.util.*; class GFG {// Function to check which// player wins the gamestatic void checkWinner(int arr[], int N){ // Stores the difference between // +ve and -ve array elements int diff = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update diff diff -= arr[i]; } // Checks if diff is even if (diff % 2 == 0) { System.out.println("A"); } else { System.out.println("B"); }}// Driver Codepublic static void main(String[] args) { // Given Input int arr[] = { 1, 2 }; int N = arr.length; // Function call to check // which player wins the game checkWinner(arr, N);}}// This code is contributed by Stream-Cipher |
C#
// C# program for the above approachusing System;class GFG{// Function to check which// player wins the gamestatic void checkWinner(int[] arr, int N){ // Stores the difference between // +ve and -ve array elements int diff = 0; // Traverse the array for(int i = 0; i < N; i++) { // Update diff diff -= arr[i]; } // Checks if diff is even if (diff % 2 == 0) { Console.Write("A"); } else { Console.Write("B"); }}// Driver Codepublic static void Main(){ // Given Input int[] arr = { 1, 2 }; int N = arr.Length; // Function call to check // which player wins the game checkWinner(arr, N);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach// Function to check which// player wins the gamefunction checkWinner(arr, N){ // Stores the difference between // +ve and -ve array elements let diff = 0; // Traverse the array for (let i = 0; i < N; i++) { // Update diff diff -= arr[i]; } // Checks if diff is even if (diff % 2 == 0) { document.write("A"); } else { document.write("B"); }}// Driver Code // Given Input let arr = [ 1, 2 ]; let N = arr.length; // Function call to check // which player wins the game checkWinner(arr, N); </script> |
B
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!