Encuentra al ganador en nim-game

Se le da una array A[] de n elementos. Hay dos jugadores Alice y Bob. Un jugador puede elegir cualquier elemento de la array y eliminarlo. Si el XOR bit a bit de todos los elementos restantes es igual a 0 después de eliminar el elemento seleccionado, entonces ese jugador pierde. Este problema es una variación del juego nim. 

Nota: Cada jugador juega alternativamente. Averigüe el ganador si ambos jugadores juegan de manera óptima. Alice comienza el juego primero. En caso de que un elemento en la array considere su valor como el XOR de la array. 

Ejemplos:  

Entrada: A[] = {3, 3, 2} 
Salida: Ganador = Bob 
Explicación: Alice puede seleccionar 2 y eliminarlo, lo que hace que XOR de la array sea igual a cero, también si Alice elige 3 para eliminar, entonces Bob puede elegir cualquiera de 2/ 3 y finalmente Alice tiene que hacer sus pasos.

Entrada: A[] = {3, 3} 
Salida: Ganador = Alice 
Explicación: Como XOR de la array ya es cero, Alice no puede seleccionar ningún elemento para eliminar y, por lo tanto, Alice es la ganadora. 
 

Comencemos la solución paso a paso. Tenemos un total de tres opciones para el XOR de array y este juego.  

1. XOR de la array ya es 0: en este caso, Alice no podrá hacer un movimiento y, por lo tanto, Alice es la ganadora.
2. XOR de la array no es cero: Ahora, en este caso tenemos dos opciones, el tamaño de la array será par o impar.
   • CASO A: Si el tamaño de la array es impar, seguro que Bob ganará el juego.
   • CASO B: Si el tamaño de la array es par, Alicia ganará el juego.

La conclusión anterior se puede probar con la ayuda de la inducción matemática.
Sea A[] = {1}, es decir, el tamaño de la array es impar y el XOR de la array no es cero: en este caso, Alice puede seleccionar el elemento 1 y luego A[] quedará vacío y, por lo tanto, el XOR de la array puede considerarse cero. Resultando Bob como ganador.
Deje que el tamaño de la array sea par y el XOR de la array no sea cero. Ahora podemos probar que Alice siempre puede encontrar un elemento para eliminar, de modo que XOR de los elementos restantes de la array no sea cero. 

Para probar esto, comencemos desde la contradicción, es decir, supongamos que cualquier elemento que deba elegir XOR de la array restante debe ser cero. 
Entonces, sea A1 X o A2 X o … An = X y n es par. 
Según nuestra hipótesis de contradicción, Ai Xor X = 0 para 1<= i <= n. 
Calcule XOR de todas las X Xor Ai (es decir, n ecuaciones). 
Después de tomar XOR de todas las n ecuaciones, tenemos X Xor X…Xor X (n veces) = 0 ya que N es par. 
Ahora, también tenemos A1 Xor A2 Xor.. An = 0 pero conocemos A1 Xor A2…Xor = X. Esto significa que tenemos al menos un elemento en una array de tamaño par tal que después de su eliminación XOR de los elementos restantes en no- cero.

Deje que el tamaño de la array sea par y el XOR de la array no sea cero. Alice no puede eliminar un elemento Ai tal que xor del número restante sea cero, porque eso hará que Bob gane. Ahora, tome el otro caso cuando el xor del número N?1 restante es distinto de cero. Como sabemos que N?1 es par y por la hipótesis de inducción, podemos decir que la posición después del movimiento actual será una posición ganadora para Bob. Por lo tanto, es una posición perdedora para Alice.

int res = 0;
for (int i = 1; i <= N; i++) {
    res ^= a[i];
}

if (res == 0)
    return "ALice";
if (N%2 == 0)
    return "Alice";
else
    return "Bob";

// CPP to find nim-game winner
#include <bits/stdc++.h>
using namespace std;
 
// function to find winner of NIM-game
string findWinner(int A[], int n)
{
    int res = 0;
    for (int i = 0; i < n; i++)
        res ^= A[i];
 
    // case when Alice is winner
    if (res == 0 || n % 2 == 0)
        return "Alice";
 
    // when Bob is winner
    else
        return "Bob";
}
 
// driver program
int main()
{
    int A[] = { 1, 4, 3, 5 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Winner = " << findWinner(A, n);
    return 0;
}

// Java to find nim-game winner
class GFG {
     
    // function to find winner of NIM-game
    static String findWinner(int A[], int n)
    {
        int res = 0;
         
        for (int i = 0; i < n; i++)
            res ^= A[i];
     
        // case when Alice is winner
        if (res == 0 || n % 2 == 0)
            return "Alice";
     
        // when Bob is winner
        else
            return "Bob";
    }
     
    //Driver code
    public static void main (String[] args)
    {
        int A[] = { 1, 4, 3, 5 };
        int n =A.length;
         
        System.out.print("Winner = "
                    + findWinner(A, n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find nim-game winner
 
# Function to find winner of NIM-game
def findWinner(A, n):
 
    res = 0
    for i in range(n):
        res ^= A[i]
 
    # case when Alice is winner
    if (res == 0 or n % 2 == 0):
        return "Alice"
 
    # when Bob is winner
    else:
        return "Bob"
 
# Driver code
A = [ 1, 4, 3, 5 ]
n = len(A)
print("Winner = ", findWinner(A, n))
 
# This code is contributed by Anant Agarwal.

// C# to find nim-game winner
using System;
 
class GFG {
     
    // function to find winner of NIM-game
    static String findWinner(int []A, int n)
    {
        int res = 0;
         
        for (int i = 0; i < n; i++)
            res ^= A[i];
     
        // case when Alice is winner
        if (res == 0 || n % 2 == 0)
            return "Alice";
     
        // when Bob is winner
        else
            return "Bob";
    }
     
    //Driver code
    public static void Main ()
    {
        int []A = { 1, 4, 3, 5 };
        int n =A.Length;
         
        Console.WriteLine("Winner = "
                    + findWinner(A, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP to find nim-game winner
 
// function to find
// winner of NIM-game
function findWinner($A, $n)
{
    $res = 0;
    for ($i = 0; $i < $n; $i++)
        $res ^= $A[$i];
 
    // case when Alice is winner
    if ($res == 0 or $n % 2 == 0)
        return "Alice";
 
    // when Bob is winner
    else
        return "Bob";
}
 
// Driver Code
$A = array(1, 4, 3, 5 );
$n = count($A);
echo "Winner = " , findWinner($A, $n);
 
// This code is contributed by vt_m.
?>

<script>
 
// JavaScript program to find nim-game winner
 
    // function to find winner of NIM-game
    function findWinner(A, n)
    {
        let res = 0;
           
        for (let i = 0; i < n; i++)
            res ^= A[i];
       
        // case when Alice is winner
        if (res == 0 || n % 2 == 0)
            return "Alice";
       
        // when Bob is winner
        else
            return "Bob";
    }
 
 
// Driver Code
 
        let A = [ 1, 4, 3, 5 ];
        let n = A.length;
           
        document.write("Winner = "
                    + findWinner(A, n));
   
</script>

Producción : 

Winner = Alice

Complejidad de tiempo : O(N) Donde N es el tamaño dado de la array. A medida que recorremos la array en un solo bucle for para N elementos. Por lo tanto, la complejidad del tiempo es O(N).

Espacio auxiliar : O (1) ya que no estamos utilizando ningún espacio adicional en la memoria, por lo que el espacio necesario es constante