Encuentra el jugador que es el último en eliminar cualquier carácter del comienzo de una string binaria

Dada una array arr[] que consta de strings binarias , la tarea es encontrar el ganador del juego cuando dos jugadores juegan de manera óptima según las siguientes reglas: 

• El jugador 1 comienza el juego.
• En cada turno, un jugador debe elegir una string que no esté vacía y eliminar un número positivo de caracteres del comienzo de la string.
• El jugador 1 solo puede elegir una string que comience con el carácter ‘0’, mientras que el jugador 2 solo puede elegir una string que comience con el carácter ‘1’.
• Un jugador que no puede hacer un movimiento pierde el juego.

Ejemplos: 

Entrada: arr[] = {“010”, “101”} 
Salida: Jugador 2 
Explicación: 
Primer movimiento del jugador 1 = {0, 101} 
Primer movimiento del jugador 2 = {0, 1} 
Segundo movimiento del jugador 1 = { 1} 
Segundo movimiento del jugador 2 = {} 
No quedan movimientos para el jugador 1. 
Por lo tanto, el jugador 2 gana. 

Entrada: arr[] = {“010”, “001”} 
Salida: Jugador 1 

Enfoque: La idea es comparar el número total de movimientos que cada jugador puede hacer si ambos juegan el juego de manera óptima. Siga los pasos a continuación: 

1. Si hay apariciones consecutivas del mismo carácter en cualquier string, simplemente reemplácelas con una sola aparición de ese carácter, ya que es óptimo eliminar todas las apariciones del carácter presente al principio.
2. Ahora, si la string tiene un elemento inicial igual que su último elemento, entonces el escenario del juego sigue siendo el mismo incluso sin esta string porque si un jugador hace un movimiento en esta string, el otro jugador hace el siguiente movimiento eliminando el personaje. de la misma cuerda, lo que da como resultado exactamente la misma posición para el primer jugador.
3. Si una string tiene un elemento inicial diferente de su último elemento, requiere que el jugador haga un movimiento adicional.
4. Entonces, solo cuente la cantidad de movimientos adicionales que cada jugador tiene que hacer.
5. El jugador que se quede sin movimientos adicionales perderá el juego.

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 player who
// loses the game
void findPlayer(string str[], int n)
{
  
    // Moves for the first player
    int move_first = 0;
  
    // Moves for the second player
    int move_sec = 0;
  
    // Iterate over array of strings
    for (int i = 0; i < n; i++) {
  
        // Check if the first and last
        // character are the same
        if (str[i][0]
            == str[i][str[i].length() - 1]) {
  
            // Check if string start and
            // end with character '0'
            if (str[i][0] == 48)
                move_first++;
            else
                move_sec++;
        }
    }
  
    // If first player have less moves
    if (move_first <= move_sec) {
        cout << "Player 2 wins";
    }
    else {
        cout << "Player 1 wins";
    }
}
  
// Driver Code
int main()
{
    // Given array of strings
    string str[] = { "010", "101" };
  
    int N = sizeof(str)
            / sizeof(str[0]);
  
    // Function Call
    findPlayer(str, N);
  
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
  
// Function to find the player who
// loses the game
static void findPlayer(String str[],
                       int n)
{
  // Moves for the
  // first player
  int move_first = 0;
 
  // Moves for the
  // second player
  int move_sec = 0;
 
  // Iterate over array
  // of Strings
  for (int i = 0; i < n - 1; i++)
  {
    // Check if the first and last
    // character are the same
    if (str[i].charAt(0) ==
        str[i].charAt(str[i].length() - 1))
    {
      // Check if String start and
      // end with character '0'
      if (str[i].charAt(0) == 48)
        move_first++;
      else
        move_sec++;
    }
  }
 
  // If first player have less moves
  if (move_first <= move_sec)
  {
    System.out.print("Player 2 wins");
  }
  else
  {
    System.out.print("Player 1 wins");
  }
}
  
// Driver Code
public static void main(String[] args)
{
  // Given array of Strings
  String str[] = {"010", "101"};
 
  int N = str[0].length();
   
  // Function Call
  findPlayer(str, N);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
  
# Function to find the player who
# loses the game
def findPlayer(str, n):
  
    # Moves for the first player
    move_first = 0
  
    # Moves for the second player
    move_sec = 0
  
    # Iterate over array of strings
    for i in range(n):
  
        # Check if the first and last
        # character are the same
        if (str[i][0] ==
            str[i][len(str[i]) - 1]):
  
            # Check if string start and
            # end with character '0'
            if (str[i][0] == 48):
                move_first += 1
            else:
                move_sec += 1
         
    # If first player have less moves
    if (move_first <= move_sec):
        print("Player 2 wins")
    else:
        print("Player 1 wins")
     
# Driver Code
 
# Given array of strings
str = [ "010", "101" ]
  
N = len(str)
  
# Function call
findPlayer(str, N)
 
# This code is contributed by sanjoy_62

// C# program for the above approach 
using System;
 
class GFG{
  
// Function to find the player who
// loses the game
static void findPlayer(string[] str, int n)
{
     
    // Moves for the first player
    int move_first = 0;
  
    // Moves for the second player
    int move_sec = 0;
  
    // Iterate over array of strings
    for(int i = 0; i < n; i++)
    {
         
        // Check if the first and last
        // character are the same
        if (str[i][0] ==
            str[i][str[i].Length - 1])
        {
             
            // Check if string start and
            // end with character '0'
            if ((str[i][0]) == 48)
                move_first++;
            else
                move_sec++;
        }
    }
  
    // If first player have less moves
    if (move_first <= move_sec)
    {
        Console.Write("Player 2 wins");
    }
    else
    {
        Console.Write("Player 1 wins");
    }
}
  
// Driver Code
public static void Main ()
{
     
    // Given array of strings
    string[] str = { "010", "101" };
  
    int N = str.Length;
  
    // Function call
    findPlayer(str, N);
}
}
 
// This code is contributed by sanjoy_62

<script>
// javascript program for the
// above approach
 
// Function to find the player who
// loses the game
function findPlayer(str, n)
{
  // Moves for the
  // first player
  let move_first = 0;
  
  // Moves for the
  // second player
  let move_sec = 0;
  
  // Iterate over array
  // of Strings
  for (let i = 0; i < n - 1; i++)
  {
    // Check if the first and last
    // character are the same
    if (str[i][0] ==
        str[i][str[i].length - 1])
    {
      // Check if String start and
      // end with character '0'
      if (str[i][0]== 48)
        move_first++;
      else
        move_sec++;
    }
  }
  
  // If first player have less moves
  if (move_first <= move_sec)
  {
    document.write("Player 2 wins");
  }
  else
  {
    document.write("Player 1 wins");
  }
}
 
  
// Driver Code
 
    // Given array of Strings
  let str = ["010", "101"];
  
  let N = str[0].length;
    
  // Function Call
  findPlayer(str, N);
           
</script>

Player 2 wins

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