Buscar bit cuya secuencia mínima se voltea hace que todos los bits sean iguales

Dada una string binaria que consta solo de 1 y 0. Encuentre el bit (la salida es 1 o 0) cuyo número mínimo de cambios de secuencia contiguos puede hacer que todos los bits de la string sean iguales.
Aquí, voltear secuencias contiguas significa voltear una substring o 0s o 1s. Por ejemplo, en la string «00011110001110», de un tirón podemos cambiar la string a «11111110001110». Los primeros tres ceros continuos se cambian a 1. 
Nota
 

  • De un tirón podemos cambiar cualquier secuencia continua de esta string.
  • Si son posibles tanto 0 como 1, imprima el último.
  • La tarea es simplemente imprimir el bit 1 o 0 para el cual los cambios mínimos de secuencia harán que todos los bits sean iguales.

Ejemplos
 

Entrada : str = “00011110001110” 
Salida : 1 
Explicación : Hay dos secuencias contiguas de 1 y tres secuencias contiguas de 0. Entonces, voltear 1 conduciría a un mínimo de volteretas.
Entrada : str = «010101100011» 
Salida : 1 
Explicación : Dado que el recuento de grupos de 0 y 1 es el mismo y 1 viene en último lugar. 
 

Enfoque ingenuo : comience a recorrer la string y tome variables denominadas groupOfOnes y otro groupOfZeros para contar los grupos de 0 y 1. Ahora, compare el conteo de grupos de unos y ceros. El que tenga el conteo menor será la respuesta.
Si ambos son iguales, la respuesta será el último carácter de la string.
Complejidad de tiempo : O(N)
Enfoque eficiente
 

  • Observe la string cuidadosamente, el carácter en el último índice de la string tendrá más grupos en la string (si el primer y el último carácter de la string son iguales). Entonces, la respuesta será otro personaje.
  • Si el primer y el último carácter no son iguales, ambos caracteres tienen el mismo número de grupos. Entonces, la respuesta será el carácter en el último índice.

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

C++

// C++ program to find which bit sequence
// to be flipped
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check which bit is to be flipped
char bitToBeFlipped(string s)
{
    // variable to store first and
    // last character of string
    char last = s[s.length() - 1];
    char first = s[0];
 
    // Check if first and last characters
    // are equal, if yes, then return
    // the character which is not at last
    if (last == first) {
        if (last == '0') {
            return '1';
        }
        else {
            return '0';
        }
    }
 
    // else return last
    else if (last != first) {
        return last;
    }
}
 
// Driver Code
int main()
{
    string s = "1101011000";
 
    cout << bitToBeFlipped(s) << endl;
 
    return 0;
}

Java

// Java program to find which bit sequence
// to be flipped
 
class GfG {
 
// Function to check which bit is to be flipped
static char bitToBeFlipped(String s)
{
    // variable to store first and
    // last character of string
    char last = s.charAt(s.length() - 1);
    char first = s.charAt(0);
 
    // Check if first and last characters
    // are equal, if yes, then return
    // the character which is not at last
    if (last == first) {
        if (last == '0') {
            return '1';
        }
        else {
            return '0';
        }
    }
 
    // else return last
    else if (last != first) {
        return last;
    }
    return last;
}
 
// Driver Code
public static void main(String[] args)
{
    String s = "1101011000";
 
    System.out.println(bitToBeFlipped(s));
}
}

Python 3

# Python 3 program to find which bit
# sequence to be flipped
 
# Function to check which bit is
# to be flipped
def bitToBeFlipped( s):
 
    # variable to store first and
    # last character of string
    last = s[len(s) - 1]
    first = s[0]
 
    # Check if first and last characters
    # are equal, if yes, then return
    # the character which is not at last
    if (last == first) :
        if (last == '0') :
            return '1'
     
        else :
            return '0'
 
    # else return last
    elif (last != first) :
        return last
 
# Driver Code
if __name__ == "__main__":
     
    s = "1101011000"
 
    print(bitToBeFlipped(s))
 
# This code is contributed by ita_c

C#

// C# program to find which bit sequence
// to be flipped
using System;
 
class GfG {
 
// Function to check which bit is to be flipped
static char bitToBeFlipped(String s)
{
    // variable to store first and
    // last character of string
    char last = s[s.Length - 1];
    char first = s[0];
 
    // Check if first and last characters
    // are equal, if yes, then return
    // the character which is not at last
    if (last == first) {
        if (last == '0') {
            return '1';
        }
        else {
            return '0';
        }
    }
 
    // else return last
    else if (last != first) {
        return last;
    }
    return last;
}
 
// Driver Code
public static void Main()
{
    string s = "1101011000";
 
    Console.WriteLine(bitToBeFlipped(s));
}
}
// This code is contributed by anuj_67..

PHP

<?php
// PHP program to find which bit sequence
// to be flipped
 
// Function to check which bit is to be flipped
function bitToBeFlipped($s)
{
    // variable to store first and
    // last character of string
    $last = $s[strlen($s) - 1];
    $first = $s[0];
 
    // Check if first and last characters
    // are equal, if yes, then return
    // the character which is not at last
    if ($last == $first)
    {
        if ($last == '0')
        {
            return '1';
        }
        else
        {
            return '0';
        }
    }
 
    // else return last
    else if ($last != $first)
    {
        return $last;
    }
}
 
 
// Driver Code
$s = "1101011000";
echo bitToBeFlipped($s);
 
// This code is contributed by ihritik
?>

Javascript

<script>
 
// JavaScript program to find which bit sequence
// to be flipped
 
// Function to check which bit is to be flipped
function bitToBeFlipped(s)
{
    // variable to store first and
    // last character of string
    let last = s[s.length - 1];
    let first = s[0];
 
    // Check if first and last characters
    // are equal, if yes, then return
    // the character which is not at last
    if (last == first) {
        if (last == '0') {
            return '1';
        }
        else {
            return '0';
        }
    }
 
    // else return last
    else if (last != first) {
        return last;
    }
}
 
// Driver Code
let s = "1101011000";
document.write(bitToBeFlipped(s),'<br>');
 
 
</script>
Producción: 

0

 

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

Publicación traducida automáticamente

Artículo escrito por barykrg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *