Encuentre al jugador que gana el juego de colocar signos + y – alternativos frente a los elementos de la array

Dada una array arr[] de longitud, N , la tarea es encontrar el ganador de un juego jugado por dos jugadores A y B de manera óptima, realizando las siguientes operaciones:

• El jugador A hace el primer movimiento.
• Los jugadores deben colocar alternativamente los signos + y – delante de los elementos de la array en sus turnos.
• Después de haber colocado signos delante de todos los elementos de la array, el jugador A gana si la diferencia de todos los elementos es par.
• De lo contrario, el jugador B gana.

Ejemplos:

Entrada: arr[] = {1, 2}
Salida: B
Explicación:
Todas las formas posibles en que se puede jugar el juego son:
(+1) – (+2) = -1 
(−1) – (+2) = – 3 
(+1) – (-2) = 3 
(-1) – (-2) = 1
Como las diferencias son impares en todas las posibilidades, gana B.

Entrada: arr[] = {1, 1, 2}
Salida: A
Explicación: 
Todas las formas posibles en que se puede jugar el juego son:
(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
Dado que las diferencias son parejas en todas las posibilidades, A gana.

Enfoque ingenuo: el enfoque más simple es generar todas las combinaciones posibles de 2 ^N en las que los signos se pueden colocar en la array y verificar para cada combinación, verificar si el jugador A puede ganar o no. Si se encuentra que es cierto para cualquier permutación, imprima A. De lo contrario, el jugador B gana.

Complejidad de Tiempo: O(2 ^N * N)
Espacio Auxiliar: O(1)

Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:

• Inicialice una variable, digamos diff , para almacenar la suma de los elementos de la array .
• Recorra la array arr[] , sobre el rango de índices [1, N] , y actualice diff restándole arr[i] . 
• Si se encuentra que diff% 2 es igual a 0 , imprima ‘A’ . De lo contrario, imprime ‘B’ .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check which
// player wins the game
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) {
        cout << "A";
    }
    else {
        cout << "B";
    }
}
 
// Driver Code
int 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 program for the
# above approach
 
# Function to check which
# player wins the game
def 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 Code
if __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 program for the
// above approach
import java.util.*;
 
class GFG
{
// Function to check which
// player wins the game
static 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 Code
public 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# program for the above approach
using System;
 
class GFG{
 
// Function to check which
// player wins the game
static 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 Code
public 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

<script>
// JavaScript program for the above approach
 
// Function to check which
// player wins the game
function 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

Complejidad temporal: O(N)
Espacio auxiliar: O(1)