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)