Último carácter restante después de la eliminación repetida del primer carácter y el cambio de caracteres de una string binaria

Dada una string binaria str de longitud N , la tarea es encontrar el último carácter eliminado de la string eliminando repetidamente el primer carácter de la string y volteando todos los caracteres de la string si el carácter eliminado es ‘0’ .

Ejemplos:

Entrada: str = “1001” 
Salida: ‘0’ 
Explicación: 
Eliminar str[0] de la string modifica str a “001”. 
Eliminar str[0] de la string modifica str a «10». 
Eliminar str[0] de la string modifica str a «0». 
Dado que el último carácter eliminado fue ‘0’, la salida requerida es ‘0’.

Entrada: str = “10010” 
Salida: ‘0’

Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre los caracteres de la string . Para cada carácter encontrado, elimine el primer carácter de la string y verifique si el carácter eliminado era ‘0’ o no. Si se determina que es cierto, invierta todos los caracteres de la string . Finalmente, imprima el carácter que se eliminó en la última iteración. Siga los pasos a continuación para resolver el problema: 

Complejidad de Tiempo: O(N ² )  
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la siguiente observación:

Caso 1: 
Supongamos que str = “XXXXXXX0X”, donde X es ‘0’ o ‘1’. 
Si se voltea el carácter str[N – 2], entonces se debe voltear str[N – 1]. 
Por lo tanto, si str[N – 2] es ‘0’, el último carácter eliminado será (‘1’ – str[N – 1] + ‘0’).
Caso 2: 
Supongamos que str = “XXXXXXX1X”, donde X es ‘0’ o ‘1. 
Si se voltea el carácter str[N – 2], entonces se debe voltear str[N – 1]. 
Por lo tanto, si str[N – 2] es ‘1’, el último carácter eliminado será str[N – 1]. 
 

Siga los pasos a continuación para resolver el problema:

• Si N es igual a 1, entonces la respuesta es str[0] , de lo contrario. 
• Compruebe si str[N – 2] (Para N>=2) es ‘1’ o no. Si se encuentra que es cierto, imprima str[N – 1].
• De lo contrario, imprime (‘1’ – str[N – 1] + ‘0’) .

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the last removed
// character from the string
char lastRemovedCharacter(string str)
{
    // Stores length of the string
    int n = str.length();
 
    // Base Case:
    if (n == 1)
        return str[0];
 
    // If the second last
    // character is '0'
    if (str[n - 2] == '0') {
 
        return ('1' - str[n - 1] + '0');
    }
 
    // If the second last
    // character is '1'
    else
        return str[n - 1];
}
 
// Driver Code
int main()
{
    string str = "10010";
    cout << lastRemovedCharacter(str);
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to find the last removed
// character from the String
static char lastRemovedCharacter(char []str)
{
    // Stores length of the String
    int n = str.length;
 
    // Base Case:
    if (n == 1)
        return str[0];
 
    // If the second last
    // character is '0'
    if (str[n - 2] == '0') {
 
        return (char)('1' - str[n - 1] + '0');
    }
 
    // If the second last
    // character is '1'
    else
        return str[n - 1];
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "10010";
    System.out.print(lastRemovedCharacter(str.toCharArray()));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to implement
# the above approach
  
# Function to find the last removed
# character from the string
def lastRemovedCharacter(str):
     
    # Stores length of the string
    n = len(str)
  
    # Base Case:
    if (n == 1):
        return ord(str[0])
  
    # If the second last
    # character is '0'
    if (str[n - 2] == '0'):
        return (ord('1') -
                ord(str[n - 1]) +
                ord('0'))
  
    # If the second last
    # character is '1'
    else:
        return ord(str[n - 1])
  
# Driver Code
if __name__ == '__main__':
     
    str = "10010"
     
    print(chr(lastRemovedCharacter(str)))
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach 
using System;
    
class GFG{
    
// Function to find the last removed
// character from the String
static char lastRemovedCharacter(char []str)
{
     
    // Stores length of the String
    int n = str.Length;
  
    // Base Case:
    if (n == 1)
        return str[0];
  
    // If the second last
    // character is '0'
    if (str[n - 2] == '0')
    {
        return (char)('1' - str[n - 1] + '0');
    }
  
    // If the second last
    // character is '1'
    else
        return str[n - 1];
}
    
// Driver Code
public static void Main()
{
    string str = "10010";
     
    Console.Write(lastRemovedCharacter(
        str.ToCharArray()));
}
}
 
// This code is contributed by code_hunt

<script>
      // JavaScript program to implement
      // the above approach
 
      // Function to find the last removed
      // character from the string
      function lastRemovedCharacter(str) {
        // Stores length of the string
        var n = str.length;
 
        // Base Case:
        if (n == 1) return str[0];
 
        // If the second last
        // character is '0'
        if (str[n - 2] == "0") {
          return "1" - str[n - 1] + "0";
        }
 
        // If the second last
        // character is '1'
        else return str[n - 1];
      }
 
      // Driver Code
      var str = "10010";
      document.write(lastRemovedCharacter(str));
    </script>

0

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)