Determinar el ganador de un juego de eliminación de caracteres de una string

Dada una string numérica str , la tarea es determinar el ganador del juego cuando dos jugadores juegan de manera óptima con la string según las condiciones dadas:

• El jugador 1 siempre comienza primero.
• En un turno, un jugador puede eliminar los elementos contiguos de la string y la cantidad de elementos eliminados se sumará a su puntuación. El jugador 1 eliminará los elementos contiguos impares y el jugador 1 eliminará los elementos contiguos pares.
• Cualquier jugador que no pueda hacer un movimiento pierde el juego.
• Después de eliminar todas las strings, el jugador con la puntuación máxima gana el juego y, si las puntuaciones son iguales, imprime «-1» .

Ejemplos:

Entrada: str = “7788” 
Salida: -1 
Explicación: 
El primer movimiento para el jugador 1 es eliminar 77 y para el jugador 2 es 88. La puntuación para ambos es 2. Por lo tanto, -1.

Entrada: str = “8822” 
Salida: Jugador 2 
Explicación: 
No hay elementos impares, por lo que el jugador 1 no puede hacer ningún movimiento, por lo que el jugador 2 gana.

Enfoque: siga los pasos a continuación para resolver el problema:

1. Cree una array A[] de tamaño 10 para almacenar la frecuencia de todos los dígitos en la string dada.
2. Itere la string dada y actualice la frecuencia de cada dígito en la array anterior.
3. Recorra la array A[] y tome dos variables como suma1 = 0 y suma2 = 0 para almacenar la suma de puntajes.
4. Incremente sum1 si el índice es impar, es decir, el turno del jugador 1; de lo contrario, incremente sum2 si el índice es par, es decir, el turno del jugador 2.
5. Después de los pasos anteriores, verifique si sum1 es igual a sum2 y luego imprima -1 ; de lo contrario, imprima la cantidad de jugadores que ganan el juego en función de la puntuación.

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 when both players play optimally
void determineWinner(string str)
{
    // Stores the frequency of all digit
    vector<int> A(10);
 
    // Stores the scores of player1
    // and player2 respectively
    int sum1 = 0, sum2 = 0;
 
    // Iterate to store frequencies
    for (int i = 0; i < str.length(); i++) {
        A[int(str[i]) - 48]++;
    }
 
    for (int i = 0; i <= 9; i++) {
 
        // Turn for the player1
        if (i % 2 != 0) {
 
            // Add score of player1
            sum1 = sum1 + A[i];
        }
        else {
 
            // Add score of player2
            sum2 = sum2 + A[i];
        }
    }
 
    // Check if its a draw
    if (sum1 == sum2) {
        cout << "-1";
    }
 
    // If score of player 1 is greater
    else if (sum1 > sum2) {
        cout << "Player 1";
    }
 
    // Otherwise
    else {
        cout << "Player 2";
    }
}
 
// Driver Code
int main()
{
    string str = "78787";
    determineWinner(str);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the winner of the
// game when both players play optimally
static void determineWinner(String str)
{
     
    // Stores the frequency of all digit
    int[] A = new int[10];
 
    // Stores the scores of player1
    // and player2 respectively
    int sum1 = 0, sum2 = 0;
 
    // Iterate to store frequencies
    for(int i = 0; i < str.length(); i++)
    {
        A[(int)str.charAt(i) - 48]++;
    }
 
    for(int i = 0; i <= 9; i++)
    {
         
        // Turn for the player1
        if (i % 2 != 0)
        {
 
            // Add score of player1
            sum1 = sum1 + A[i];
        }
        else
        {
 
            // Add score of player2
            sum2 = sum2 + A[i];
        }
    }
 
    // Check if its a draw
    if (sum1 == sum2)
    {
        System.out.print("-1");
    }
 
    // If score of player 1 is greater
    else if (sum1 > sum2)
    {
        System.out.print("Player 1");
    }
 
    // Otherwise
    else
    {
        System.out.print("Player 2");
    }
}
 
// Driver code
public static void main (String[] args)
{
    String str = "78787";
     
    determineWinner(str);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function to find the winner of the
# game when both players play optimally
def determineWinner(str):
 
    # Stores the frequency of all digit
    A = [0 for i in range(9)];
 
    # Stores the scores of player1
    # and player2 respectively
    sum1 = 0; sum2 = 0;
 
    # Iterate to store frequencies
    for i in range(0, len(str)):
        A[int(str[i])] += 1;
     
    for i in range(0, 9):
 
        # Turn for the player1
        if (i % 2 != 0):
 
            # Add score of player1
            sum1 = sum1 + A[i];
        else:
 
            # Add score of player2
            sum2 = sum2 + A[i];
         
    # Check if its a draw
    if (sum1 == sum2):
        print("-1");
     
    # If score of player 1 is greater
    elif(sum1 > sum2):
        print("Player 1");
     
    # Otherwise
    else:
        print("Player 2");
     
# Driver code
if __name__ == '__main__':
     
    str = "78787";
 
    determineWinner(str);
     
# This code is contributed by Amit Katiyar

// C# program for the above approach
using System;
class GFG{
 
// Function to find the winner of the
// game when both players play optimally
static void determineWinner(String str)
{
     
    // Stores the frequency of all digit
    int[] A = new int[10];
 
    // Stores the scores of player1
    // and player2 respectively
    int sum1 = 0, sum2 = 0;
 
    // Iterate to store frequencies
    for(int i = 0; i < str.Length; i++)
    {
        A[(int)str[i] - 48]++;
    }
 
    for(int i = 0; i <= 9; i++)
    {
         
        // Turn for the player1
        if (i % 2 != 0)
        {
 
            // Add score of player1
            sum1 = sum1 + A[i];
        }
        else
        {
 
            // Add score of player2
            sum2 = sum2 + A[i];
        }
    }
 
    // Check if its a draw
    if (sum1 == sum2)
    {
        Console.Write("-1");
    }
 
    // If score of player 1 is greater
    else if (sum1 > sum2)
    {
        Console.Write("Player 1");
    }
 
    // Otherwise
    else
    {
        Console.Write("Player 2");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "78787";
     
    determineWinner(str);
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the winner of the
// game when both players play optimally
function determineWinner(str)
{
       
    // Stores the frequency of all digit
    let A = Array.from({length: 10}, (_, i) => 0);
   
    // Stores the scores of player1
    // and player2 respectively
    let sum1 = 0, sum2 = 0;
   
    // Iterate to store frequencies
    for(let i = 0; i < str.length; i++)
    {
        A[str[i].charCodeAt() - 48]++;
    }
   
    for(let i = 0; i <= 9; i++)
    {
           
        // Turn for the player1
        if (i % 2 != 0)
        {
   
            // Add score of player1
            sum1 = sum1 + A[i];
        }
        else
        {
   
            // Add score of player2
            sum2 = sum2 + A[i];
        }
    }
   
    // Check if its a draw
    if (sum1 == sum2)
    {
        document.write("-1");
    }
   
    // If score of player 1 is greater
    else if (sum1 > sum2)
    {
        document.write("Player 1");
    }
   
    // Otherwise
    else
    {
        document.write("Player 2");
    }
}
 
// Driver code
 
    let str = "78787";
       
    determineWinner(str);
 
</script>

Player 1

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