Dada la string binaria str , la tarea es encontrar la cantidad mínima de caracteres necesarios para voltear para hacer todos 1 s a la derecha y 0 s a la izquierda.
Ejemplos:
Entrada: str = “100101”
Salida: 2
Explicación:
Voltear str[0] y str[4] modifica str = “000111”. Por lo tanto, la salida requerida es 2.Entrada: S = “00101001”
Salida: 2
Explicación:
Voltear str[2] y str[4] modifica str = “00000001”. Por lo tanto, la salida requerida es 2.
Enfoque: La idea es contar el número de 0 en el lado derecho de cada índice de la string y contar el número de 1 en el lado izquierdo de cada índice de la string. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntzero , para almacenar el recuento total de 0 s en la string dada.
- Recorre la string y cuenta el número total de 0 s en la string dada.
- Si cntzero en la string dada es 0 , o igual a la longitud de la string, el resultado será 0 .
- Recorre la string y para cada índice, encuentra la suma de la cuenta de 1 s en el lado izquierdo del índice y la cuenta de 0 s en el lado derecho del índice.
- Encuentre el valor mínimo de todas las sumas obtenidas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum count
// of flips required to make all 1s on
// the right and all 0s on the left of
// the given string
int minimumCntOfFlipsRequired(string str)
{
// Stores length of str
int n = str.length();
// Store count of 0s in the string
int zeros = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
// If current character is 0
if (str[i] == '0') {
// Update zeros
zeros++;
}
}
// If count of 0s in the string
// is 0 or n
if (zeros == 0 || zeros == n) {
return 0;
}
// Store minimum count of flips
// required to make all 0s on
// the left and all 1s on the right
int minFlips = INT_MAX;
// Stores count of 1s on the left
// of each index
int currOnes = 0;
// Stores count of flips required to make
// string monotonically increasing
int flips;
// Traverse the string
for (int i = 0; i < n; i++) {
// If current character
// is 1
if (str[i] == '1') {
// Update currOnes
currOnes++;
}
// Update flips
flips = currOnes + (zeros - (i + 1 - currOnes));
// Update the minimum
// count of flips
minFlips = min(minFlips, flips);
}
return minFlips;
}
// Driver Code
int main()
{
string str = "100101";
cout << minimumCntOfFlipsRequired(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG {
// Function to find the minimum count of flips
// required to make all 1s on the right and
// all 0s on the left of the given string
public static int minimumCntOfFlipsRequired(
String str)
{
// Stores length of str
int n = str.length();
// Store count of 0s in the string
int zeros = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
// If current character is 0
if (str.charAt(i) == '0') {
// Update zeros
zeros++;
}
}
// If count of 0s in the string
// is 0 or n
if (zeros == 0 || zeros == n) {
return 0;
}
// Store minimum count of flips
// required to make all 0s on
// the left and 1s on the right
int minFlips = Integer.MAX_VALUE;
// Stores count of 1s on the left
// side of each index
int currOnes = 0;
// Stores count of flips required to make
// all 0s on the left and 1s on the right
int flips;
// Traverse the string
for (int i = 0; i < n; i++) {
// If current character is 1
if (str.charAt(i) == '1') {
// Update currOnes
currOnes++;
}
// Update flips
flips = currOnes + (zeros - (i + 1 - currOnes));
// Update the minimum
// count of flips
minFlips = Math.min(minFlips, flips);
}
return minFlips;
}
// Driver code
public static void main(String[] args)
{
String s1 = "100101";
System.out.println(minimumCntOfFlipsRequired(s1));
}
}
Python3
# Python3 program to implement # the above approach # Function to find the minimum count # of flips required to make all 1s on # the right and all 0s on the left of # the given string def minimumCntOfFlipsRequired(str): # Stores length of str n = len(str); # Store count of 0s in the string zeros = 0; # Traverse the string for i in range(n): # If current character # is 0 if (str[i] == '0'): # Update zeros zeros += 1; # If count of 0s in the string # is 0 or n if (zeros == 0 or zeros == n): return 0; # Store minimum count of flips # required to make all 0s on the # left and all 1s on the right minFlips = 10000001; # Stores count of 1s on the left # of each index currOnes = 0; # Stores count of flips required to make # all 0s on the left and all 1s on the right flips = 0; # Traverse the string for i in range(n): # If current character is 1 if (str[i] == '1'): # Update currOnes currOnes += 1; # Update flips flips = currOnes + (zeros - (i + 1 - currOnes)); # Update the minimum # count of flips minFlips = min(minFlips, flips); return minFlips; # Driver Code if __name__ == '__main__': str = "100101"; print(minimumCntOfFlipsRequired(str));
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the minimum count of flips
// required to make all 1s on the right and
// all 0s on the left of the given string
public static int minimumCntOfFlipsRequired(string str)
{
// Stores length of str
int n = str.Length;
// Store count of 0s in the string
int zeros = 0;
// Traverse the string
for(int i = 0; i < n; i++)
{
// If current character is 0
if (str[i] == '0')
{
// Update zeros
zeros++;
}
}
// If count of 0s in the string
// is 0 or n
if (zeros == 0 || zeros == n)
{
return 0;
}
// Store minimum count of flips
// required to make all 0s on
// the left and 1s on the right
int minFlips = Int32.MaxValue;
// Stores count of 1s on the left
// side of each index
int currOnes = 0;
// Stores count of flips required
// to make all 0s on the left and
// 1s on the right
int flips;
// Traverse the string
for(int i = 0; i < n; i++)
{
// If current character is 1
if (str[i] == '1')
{
// Update currOnes
currOnes++;
}
// Update flips
flips = currOnes +
(zeros - (i + 1 - currOnes));
// Update the minimum
// count of flips
minFlips = Math.Min(minFlips, flips);
}
return minFlips;
}
// Driver code
public static void Main()
{
string s1 = "100101";
Console.WriteLine(minimumCntOfFlipsRequired(s1));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the minimum count of flips
// required to make all 1s on the right and
// all 0s on the left of the given string
function minimumCntOfFlipsRequired(str)
{
// Stores length of str
let n = str.length;
// Store count of 0s in the string
let zeros = 0;
// Traverse the string
for (let i = 0; i < n; i++) {
// If current character is 0
if (str[i] == '0') {
// Update zeros
zeros++;
}
}
// If count of 0s in the string
// is 0 or n
if (zeros == 0 || zeros == n) {
return 0;
}
// Store minimum count of flips
// required to make all 0s on
// the left and 1s on the right
let minFlips = Number.MAX_VALUE;
// Stores count of 1s on the left
// side of each index
let currOnes = 0;
// Stores count of flips required to make
// all 0s on the left and 1s on the right
let flips;
// Traverse the string
for (let i = 0; i < n; i++) {
// If current character is 1
if (str[i] == '1') {
// Update currOnes
currOnes++;
}
// Update flips
flips = currOnes + (zeros - (i + 1 - currOnes));
// Update the minimum
// count of flips
minFlips = Math.min(minFlips, flips);
}
return minFlips;
}
// Driver Code
let s1 = "100101";
document.write(minimumCntOfFlipsRequired(s1));
</script>
Producción
2
Complejidad de tiempo: O(N), donde N es la longitud de la string
Espacio auxiliar: O(1)