Encuentra el jugador para poder reemplazar el último elemento que se puede reemplazar por sus divisores

Dada una array arr[] que consta de N enteros y dos jugadores A y B jugando juntos realizando las siguientes operaciones:

• Elija un número entero de arr[] y reemplace ese número con uno de sus divisores.
• Un entero previamente seleccionado no se puede volver a elegir.
• Como el 1 no tiene otro divisor que no sea él mismo, un jugador no puede reemplazar el 1 con ningún otro número. Por lo tanto, cuando la array consta de solo 1 s, el jugador que no puede hacer ningún movimiento pierde el juego.
• Ambos jugadores jugarán de manera óptima y A hace el primer movimiento del juego.

La tarea es encontrar al ganador del juego.

Ejemplos:

Entrada: arr[] = {24, 45, 45, 24}
Salida: B 
Explicación: 
El jugador A reemplaza 24 en el primer índice con 1. Dado que 1 es un divisor de 24. arr[] = {1, 45, 45 , 24} El
jugador B reemplaza 24 en el último índice con 1. Dado que 1 es un divisor de 24. arr[] = {1, 45, 45, 1} El
jugador A reemplaza 45 en el segundo índice con 1. Dado que, 1 es un divisor de 45. arr[] = {1, 1, 45, 24} El
jugador B reemplaza 45 en el tercer índice con 1. Dado que 1 es un divisor de 45. arr[] = {1, 1, 1, 1} El
jugador A no puede hacer un movimiento ahora, ya que todos los elementos son 1. Por lo tanto, el jugador B gana el juego.

Entrada: arr[] = {18, 6}
Salida: B

Planteamiento: El problema se puede resolver en base a una simple observación: 

• Dado que 1 es un divisor de todos los enteros, por lo tanto, reemplace cada elemento de la array con 1 en cada operación.
• Por lo tanto, si la array consta de un número par de elementos, entonces el jugador B gana.
• De lo contrario, el jugador A gana.

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 find the winner
// of the game played based on
// given conditions
void winner(int arr[], int N)
{
 
    // A wins if size of array is odd
    if (N % 2 == 1) {
        cout << "A";
    }
   
    // Otherwise, B wins
    else {
        cout << "B";
    }
}
 
// Driver Code
int main()
{
    // Input array
    int arr[] = { 24, 45, 45, 24 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    winner(arr, N);
}

// Java program for the above approach
class GFG{
 
// Function to find the winner
// of the game played based on
// given conditions
static void winner(int arr[], int N)
{
     
    // A wins if size of array is odd
    if (N % 2 == 1)
    {
        System.out.print("A");
    }
   
    // Otherwise, B wins
    else
    {
        System.out.print("B");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input array
    int arr[] = { 24, 45, 45, 24 };
 
    // Size of the array
    int N = arr.length;
 
    winner(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to find the winner
# of the game played based on
# given conditions
def winner(arr, N):
 
    # A wins if size of array is odd
    if (N % 2 == 1):
        print ("A")
     
    # Otherwise, B wins
    else:
        print ("B")
 
# Driver Code
if __name__ == '__main__':
   
    # Input array
    arr = [24, 45, 45, 24]
 
    # Size of the array
    N = len(arr)
    winner(arr, N)
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
public class GFG
{
 
// Function to find the winner
// of the game played based on
// given conditions
static void winner(int []arr, int N)
{
     
    // A wins if size of array is odd
    if (N % 2 == 1)
    {
        Console.Write("A");
    }
   
    // Otherwise, B wins
    else
    {
        Console.Write("B");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Input array
    int []arr = { 24, 45, 45, 24 };
 
    // Size of the array
    int N = arr.Length;
 
    winner(arr, N);
}
}
 
// This code contributed by shikhasingrajput

<script>
      // JavaScript program for the above approach
      // Function to find the winner
      // of the game played based on
      // given conditions
      function winner(arr, N) {
        // A wins if size of array is odd
        if (N % 2 === 1) {
          document.write("A");
        }
 
        // Otherwise, B wins
        else {
          document.write("B");
        }
      }
 
      // Driver Code
      // Input array
      var arr = [24, 45, 45, 24];
 
      // Size of the array
      var N = arr.length;
      winner(arr, N);
       
      // This code is contributed by rdtank.
    </script>

B

Complejidad de tiempo: O(N), donde N es el tamaño de la array.
Espacio Auxiliar : O(1)