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>
0
Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)