Dada una string binaria S , la tarea es encontrar el número mínimo de caracteres necesarios para invertir para que la string binaria dada aumente.
Ejemplo:
Entrada: S = “00110”
Salida: 1
Explicación: Voltear S[4] = ‘0’ a ‘1’ de la string modifica la string dada a “00111”. Por lo tanto, el número mínimo de lanzamientos necesarios es 1.Entrada: S = “010110”
Salida: 2
Enfoque: el problema dado se puede resolver usando a basado en las observaciones de que la string resultante que aumenta monótonamente después de cualquier número de vueltas tendrá la forma (‘0’*p + ‘1’*q) , donde p y q son el conteo de 0s y 1s respectivamente en la string modificada. La idea es atravesar la string S dada y para cada índice, modifico la substring S[0, i) a 0 y la substring S[i, N) a 1 y encuentro los cambios mínimos requeridos en consecuencia. Siga los pasos a continuación para resolver el problema:
- Encuentre el recuento de 0 en la string binaria S dada y guárdelo en una variable countZero .
- Inicialice la variable, diga minFlips como (N – cntZero) que almacena la cantidad mínima de volteretas requeridas.
- Inicialice la variable, diga cntOne como 0 que almacena el recuento de 1 en la string mientras la atraviesa.
- Atraviese la string S dada y realice los siguientes pasos:
- Si el carácter S[i] es 0 , disminuya el valor de countZero en 1 .
- De lo contrario, actualice el valor de minFlips como el mínimo de minFlips y (countZero + countOne) e incremente el valor de countOne en 1 .
- Después de completar los pasos anteriores, imprima el valor de minFlips como resultado.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach;
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of
// flips required to make string increasing
int minimumFlips(string s)
{
// Length of s
int n = s.size();
// Total number of zero in s
int cnt0 = count(s.begin(), s.end(), '0');
// Stores count of 1s till ith index
int cnt1 = 0;
// stores the minimum count of flip
int res = n - cnt0;
// Traverse the given string
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
cnt0 -= 1;
}
// Update the value of res
// and count of 1s
else if (s[i] == '1') {
res = min(res, cnt1 + cnt0);
cnt1++;
}
}
// Return the minimum number
// of flips
return res;
}
// Driver code
int main()
{
// Given string
string S = "000110";
// function call
cout << minimumFlips(S);
return 0;
}
// This code is contributed by parthmanchanda81
Java
// Java program for the above approach;
import java.util.*;
class GFG
{
// Function to find the minimum number of
// flips required to make String increasing
static int minimumFlips(String s) {
// Length of s
int n = s.length();
// Total number of zero in s
int cnt0 = count(s, '0');
// Stores count of 1s till ith index
int cnt1 = 0;
// stores the minimum count of flip
int res = n - cnt0;
// Traverse the given String
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
cnt0 -= 1;
}
// Update the value of res
// and count of 1s
else if (s.charAt(i) == '1') {
res = Math.min(res, cnt1 + cnt0);
cnt1++;
}
}
// Return the minimum number
// of flips
return res;
}
private static int count(String s, char c) {
int ans = 0;
for (char i : s.toCharArray())
if (c == i)
ans++;
return ans;
}
// Driver code
public static void main(String[] args) {
// Given String
String S = "000110";
// function call
System.out.print(minimumFlips(S));
}
}
// This code is contributed by Princi Singh
Python3
# Python program for the above approach
# Function to find the minimum number of
# flips required to make string increasing
def minimumFlips(s):
# Length of s
n = len(s)
# Total number of zero in s
cnt0 = s.count('0')
# Stores count of 1s till ith index
cnt1 = 0
# Stores the minimum count of flips
res = n - cnt0
# Traverse the given string S
for i in range(n):
if s[i] == '0':
cnt0 -= 1
elif s[i] == '1':
# Update the value of res
# and count of 1s
res = min(res, cnt1 + cnt0)
cnt1 += 1
# Return the minimum number
# of flips
return res
# Driver Code
S = '000110'
# Function Call
print(minimumFlips(S))
C#
using System;
public class GFG {
// Function to find the minimum number of
// flips required to make String increasing
static int minimumFlips(String s)
{
// Length of s
int n = s.Length;
// Total number of zero in s
int cnt0 = count(s, '0');
// Stores count of 1s till ith index
int cnt1 = 0;
// stores the minimum count of flip
int res = n - cnt0;
// Traverse the given String
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
cnt0 -= 1;
}
// Update the value of res
// and count of 1s
else if (s[i] == '1') {
res = Math.Min(res, cnt1 + cnt0);
cnt1++;
}
}
// Return the minimum number
// of flips
return res;
}
private static int count(String s, char c)
{
int ans = 0;
for (int j = 0; j < s.Length; j++) {
char i = s[j];
if (c == i)
ans++;
}
return ans;
}
// Driver code
static public void Main()
{
// Given String
String S = "000110";
// function call
Console.Write(minimumFlips(S));
}
}
// This code is contributed by maddler.
Javascript
<script>
// JavaScript program for the above approach;
// Function to find the minimum number of
// flips required to make string increasing
function minimumFlips(s) {
// Length of s
let n = s.length;
// Total number of zero in s
let i;
let cnt0 = 0;
for (i = 0; i < n; i++) {
if (s[i] == '0')
cnt0++;
}
// Stores count of 1s till ith index
let cnt1 = 0
// Stores the minimum count of flips
let res = n - cnt0
// Traverse the given string S
for (i = 0; i < n; i++)
if (s[i] == '0') {
cnt0 -= 1
}
else if (s[i] == '1') {
// Update the value of res
// and count of 1s
res = Math.min(res, cnt1 + cnt0)
cnt1 += 1
}
// Return the minimum number
// of flips
return res
}
// Driver Code
S = '000110'
// Function Call
document.write(minimumFlips(S))
// This code is contributed by Potta Lokesh
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por adityamutharia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA