Dada una string binaria circular S de tamaño N , la tarea es contar el número mínimo de 0 s consecutivos necesarios para eliminar de modo que la string contenga solo 1 s.
Una string circular es una string cuyo primer y último carácter se consideran adyacentes entre sí.
Ejemplos:
Entrada: S = “11010001”
Salida: 2
Explicación:
elimine la substring {S[2]}. Ahora, la string se modifica a «1110001».
Elimina la substring {S[3], …, S[5]} de 0s consecutivos. Ahora, la string se modifica a «1111».
Por lo tanto, el recuento mínimo de eliminaciones requeridas es 2.Entrada: S = “00110000”
Salida: 1
Enfoque: La idea para resolver el problema dado es atravesar la string dada y contar el número de substrings que tienen el mismo número de 0 s, digamos C . Ahora, si el primero y el último carácter de la string son ‘0’ , imprima el valor de (C – 1) como el número mínimo de eliminaciones requeridas. De lo contrario, imprima el valor de C como resultado.
Nota: Si la string dada contiene solo 0 , entonces el número mínimo de eliminaciones requeridas es 1 . Considere este caso por separado.
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 count minimum number of
// removal of consecutive 0s required to
// make binary string consists only of 1s
int minRemovals(string str, int N)
{
// Stores the count of removals
int ans = 0;
bool X = false;
// Traverse the string S
for (int i = 0; i < N; i++) {
// If the current character is '0'
if (str[i] == '0') {
ans++;
// Traverse until consecutive
// characters are only '0's
while (str[i] == '0') {
i++;
}
}
else {
X = true;
}
}
// If the binary string only
// contains 1s, then return 1
if (!X)
return 1;
// If the first and the last
// characters are 0
if (str[0] == '0'
and str[N - 1] == '0') {
ans--;
}
// Return the resultant count
return ans;
}
// Driver Code
int main()
{
string S = "11010001";
int N = S.size();
cout << minRemovals(S, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to count minimum number of
// removal of consecutive 0s required to
// make binary string consists only of 1s
static int minRemovals(String str, int N)
{
// Stores the count of removals
int ans = 0;
boolean X = false;
// Traverse the string S
for(int i = 0; i < N; i++)
{
// If the current character is '0'
if (str.charAt(i) == '0')
{
ans++;
// Traverse until consecutive
// characters are only '0's
while (i < N && str.charAt(i) == '0')
{
i++;
}
}
else
{
X = true;
}
}
// If the binary string only
// contains 1s, then return 1
if (!X)
return 1;
// If the first and the last
// characters are 0
if (str.charAt(0) == '0' &&
str.charAt(N - 1) == '0')
{
ans--;
}
// Return the resultant count
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "11010001";
int N = S.length();
System.out.println(minRemovals(S, N));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to count minimum number of # removal of consecutive 0s required to # make binary string consists only of 1s def minRemovals(str, N): # Stores the count of removals ans = 0 X = False # Traverse the string S i = 0 while i < N: # If the current character is '0' if (str[i] == '0'): ans += 1 # Traverse until consecutive # characters are only '0's while (str[i] == '0'): i += 1 else: X = True i += 1 # If the binary string only # contains 1s, then return 1 if (not X): return 1 # If the first and the last # characters are 0 if (str[0] == '0' and str[N - 1] == '0'): ans -= 1 # Return the resultant count return ans # Driver Code S = "11010001" N = len(S) print(minRemovals(S, N)) # This code is contributed by rohan07
C#
// C# program for the above approach
using System;
class GFG {
// Function to count minimum number of
// removal of consecutive 0s required to
// make binary string consists only of 1s
static int minRemovals(string str, int N)
{
// Stores the count of removals
int ans = 0;
bool X = false;
// Traverse the string S
for (int i = 0; i < N; i++) {
// If the current character is '0'
if (str[i] == '0') {
ans++;
// Traverse until consecutive
// characters are only '0's
while (str[i] == '0') {
i++;
}
}
else {
X = true;
}
}
// If the binary string only
// contains 1s, then return 1
if (!X)
return 1;
// If the first and the last
// characters are 0
if (str[0] == '0' && str[N - 1] == '0') {
ans--;
}
// Return the resultant count
return ans;
}
// Driver Code
public static void Main()
{
string S = "11010001";
int N = S.Length;
Console.Write(minRemovals(S, N));
}
}
// This code is contributed by subham348.
Javascript
<script>
// js program for the above approach
// Function to count minimum number of
// removal of consecutive 0s required to
// make binary consists only of 1s
function minRemovals(str, N)
{
// Stores the count of removals
let ans = 0;
let X = false;
// Traverse the S
for (i = 0; i < N; i++) {
// If the current character is '0'
if (str[i] == '0') {
ans++;
// Traverse until consecutive
// characters are only '0's
while (str[i] == '0') {
i++;
}
}
else {
X = true;
}
}
// If the binary only
// contains 1s, then return 1
if (!X)
return 1;
// If the first and the last
// characters are 0
if (str[0] == '0' && str[N - 1] == '0') {
ans--;
}
// Return the resultant count
return ans;
}
// Driver Code
let S = "11010001";
let N = S.length;
document.write(minRemovals(S, N));
// This code is contributed by mohit kumar 29.
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA