Dada una string binaria S de tamaño N , la tarea es encontrar los números mínimos de 0 que deben eliminarse de la string S de manera que todos los 1 ocurran consecutivamente.
Ejemplos:
Entrada: S = “010001011”
Salida: 4
Explicación:
Eliminar los caracteres { S[2], S[3], S[4], S[6] } de la string S modifica la string S a “01111”.
Por lo tanto, la salida requerida es 4.Entrada: S = “011110000”
Salida: 0
Explicación:
Todos los 1 en S ya se agrupan, por lo tanto, la salida requerida es 0.
Enfoque: el problema dado se puede resolver observando el hecho de que eliminar los ceros iniciales y finales en la string no minimiza la cantidad de ceros que deben eliminarse. Por lo tanto, la idea es encontrar la primera y la última aparición de 1 en la string S y encontrar la cantidad de 0 entre ellos. Siga los pasos a continuación para resolver el problema:
- Itere sobre los caracteres de la string, S de izquierda a derecha y encuentre el índice de la primera aparición de 1 s en la string dada, digamos X .
- Recorra la string de derecha a izquierda y encuentre el índice de la última aparición de 1 s en la string dada, digamos Y .
- Después de completar los pasos anteriores, imprima el recuento de 0 entre el índice X e Y como resultado.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum count of
// 0s removed from the string S such
// that all 1s occurs consecutively
void makeContiguous(string S, int N)
{
// Stores the first and the last
// occurrence of 1
int fst_occur, lst_occur;
// Iterate over the characters
// the string, S
for (int x = 0; x < N; x++) {
// If current character
// is '1'
if (S[x] == '1') {
// Update fst_occur
fst_occur = x;
break;
}
}
// Iterate over the characters
// the string, S
for (int x = N - 1; x >= 0; x--) {
// If current character
// is '1'
if (S[x] == '1') {
// Update lst_occur
lst_occur = x;
break;
}
}
// Stores the count of 0s between
// fst_occur and lst_occur
int count = 0;
// Iterate over the characters of S
// between fst_occur and lst_occur
for (int x = fst_occur;
x <= lst_occur; x++) {
// If current character is '0'
if (S[x] == '0') {
// Update count
count++;
}
}
// Print the resultant minimum count
cout << count;
}
// Driver Code
int main()
{
string S = "010001011";
int N = S.size();
makeContiguous(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find minimum count of
// 0s removed from the String S such
// that all 1s occurs consecutively
static void makeContiguous(String S, int N)
{
// Stores the first and the last
// occurrence of 1
int fst_occur=0, lst_occur=0;
// Iterate over the characters
// the String, S
for (int x = 0; x < N; x++) {
// If current character
// is '1'
if (S.charAt(x) == '1') {
// Update fst_occur
fst_occur = x;
break;
}
}
// Iterate over the characters
// the String, S
for (int x = N - 1; x >= 0; x--) {
// If current character
// is '1'
if (S.charAt(x) == '1') {
// Update lst_occur
lst_occur = x;
break;
}
}
// Stores the count of 0s between
// fst_occur and lst_occur
int count = 0;
// Iterate over the characters of S
// between fst_occur and lst_occur
for (int x = fst_occur; x <= lst_occur; x++) {
// If current character is '0'
if (S.charAt(x) == '0') {
// Update count
count++;
}
}
// Print the resultant minimum count
System.out.print(count);
}
// Driver Code
public static void main(String[] args)
{
String S = "010001011";
int N = S.length();
makeContiguous(S, N);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to find minimum count of # 0s removed from the string S such # that all 1s occurs consecutively def makeContiguous(S, N): # Stores the first and the last # occurrence of 1 fst_occur = 0 lst_occur = 0 # Iterate over the characters # the string, S for x in range(N): # If current character # is '1' if (S[x] == '1'): # Update fst_occur fst_occur = x break # Iterate over the characters # the string, S x = N - 1 while(x >= 0): # If current character # is '1' if (S[x] == '1'): # Update lst_occur lst_occur = x break x -= 1 # Stores the count of 0s between # fst_occur and lst_occur count = 0 # Iterate over the characters of S # between fst_occur and lst_occur for x in range(fst_occur,lst_occur+1,1): # If current character is '0' if (S[x] == '0'): # Update count count += 1 # Print the resultant minimum count print(count) # Driver Code if __name__ == '__main__': S = "010001011" N = len(S) makeContiguous(S, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find minimum count of
// 0s removed from the string S such
// that all 1s occurs consecutively
static void makeContiguous(string S, int N)
{
// Stores the first and the last
// occurrence of 1
int fst_occur = 0, lst_occur = 0;
// Iterate over the characters
// the string, S
for(int x = 0; x < N; x++)
{
// If current character
// is '1'
if (S[x] == '1')
{
// Update fst_occur
fst_occur = x;
break;
}
}
// Iterate over the characters
// the string, S
for(int x = N - 1; x >= 0; x--)
{
// If current character
// is '1'
if (S[x] == '1')
{
// Update lst_occur
lst_occur = x;
break;
}
}
// Stores the count of 0s between
// fst_occur and lst_occur
int count = 0;
// Iterate over the characters of S
// between fst_occur and lst_occur
for(int x = fst_occur; x <= lst_occur; x++)
{
// If current character is '0'
if (S[x] == '0')
{
// Update count
count++;
}
}
// Print the resultant minimum count
Console.Write(count);
}
// Driver Code
public static void Main()
{
string S = "010001011";
int N = S.Length;
makeContiguous(S, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// javascript program for the above approach
// Function to find minimum count of
// 0s removed from the String S such
// that all 1s occurs consecutively
function makeContiguous( S , N)
{
// Stores the first and the last
// occurrence of 1
var fst_occur = 0, lst_occur = 0;
// Iterate over the characters
// the String, S
for (var x = 0; x < N; x++) {
// If current character
// is '1'
if (S.charAt(x) == '1') {
// Update fst_occur
fst_occur = x;
break;
}
}
// Iterate over the characters
// the String, S
for (var x = N - 1; x >= 0; x--) {
// If current character
// is '1'
if (S.charAt(x) == '1') {
// Update lst_occur
lst_occur = x;
break;
}
}
// Stores the count of 0s between
// fst_occur and lst_occur
var count = 0;
// Iterate over the characters of S
// between fst_occur and lst_occur
for (x = fst_occur; x <= lst_occur; x++) {
// If current character is '0'
if (S.charAt(x) == '0') {
// Update count
count++;
}
}
// Print the resultant minimum count
document.write(count);
}
// Driver Code
var S = "010001011";
var N = S.length;
makeContiguous(S, N);
// This code is contributed by umadevi9616
</script>
Producción
4