Dada una string binaria S de tamaño N , la tarea es maximizar la suma de la cuenta de 0 s consecutivos presentes al principio y al final de cualquiera de las rotaciones de la string dada S .
Ejemplos:
Entrada: S = “1001”
Salida: 2
Explicación:
Todas las rotaciones posibles de la string son:
“1001”: Cuenta de 0s al inicio = 0; al final = 0. Suma= 0 + 0 = 0.
“0011”: Cuenta de 0s al inicio = 2; al final = 0. Suma = 2 + 0=2
“0110”: Cuenta de 0s al inicio = 1; al final = 1. Suma= 1 + 1 = 2.
“1100”: Cuenta de 0s al inicio = 0; al final = 2. Suma = 0 + 2 = 2
Por lo tanto, la suma máxima posible es 2.Entrada: S = “01010”
Salida: 2
Explicación:
Todas las rotaciones posibles de la string son:
“01010”: Cuenta de 0s al inicio = 1; al final = 1. Suma= 1+1=1
“10100”: Cuenta de 0s al inicio = 0; al final = 2. Suma= 0+2=2
“01001”: Cuenta de 0s al inicio = 1; al final = 0. Suma= 1+0=1
“10010”: Cuenta de 0s al inicio = 0; al final = 1. Suma= 0+1=1
“00101”: Cuenta de 0s al inicio = 2; al final = 0. Suma= 2+0=2
Por lo tanto, la suma máxima posible es 2.
Enfoque ingenuo: la idea más simple es generar todas las rotaciones de la string dada y, para cada rotación, contar el número de 0 presentes al principio y al final de la string y calcular su suma. Finalmente, imprima la suma máxima obtenida.
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 maximum sum of
// consecutive 0s present at the start
// and end of a string present in any
// of the rotations of the given string
void findMaximumZeros(string str, int n)
{
// Check if all the characters
// in the string are 0
int c0 = 0;
// Iterate over characters
// of the string
for (int i = 0; i < n; ++i) {
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n) {
// Print n as the result
cout << n;
return;
}
// Concatenate the string
// with itself
string s = str + str;
// Stores the required result
int mx = 0;
// Generate all rotations of the string
for (int i = 0; i < n; ++i) {
// Store the number of consecutive 0s
// at the start and end of the string
int cs = 0;
int ce = 0;
// Count 0s present at the start
for (int j = i; j < i + n; ++j) {
if (s[j] == '0')
cs++;
else
break;
}
// Count 0s present at the end
for (int j = i + n - 1; j >= i; --j) {
if (s[j] == '0')
ce++;
else
break;
}
// Calculate the sum
int val = cs + ce;
// Update the overall
// maximum sum
mx = max(val, mx);
}
// Print the result
cout << mx;
}
// Driver Code
int main()
{
// Given string
string s = "1001";
// Store the size of the string
int n = s.size();
findMaximumZeros(s, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of a string present in any
// of the rotations of the given string
static void findMaximumZeros(String str, int n)
{
// Check if all the characters
// in the string are 0
int c0 = 0;
// Iterate over characters
// of the string
for(int i = 0; i < n; ++i)
{
if (str.charAt(i) == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n)
{
// Print n as the result
System.out.print(n);
return;
}
// Concatenate the string
// with itself
String s = str + str;
// Stores the required result
int mx = 0;
// Generate all rotations of the string
for(int i = 0; i < n; ++i)
{
// Store the number of consecutive 0s
// at the start and end of the string
int cs = 0;
int ce = 0;
// Count 0s present at the start
for(int j = i; j < i + n; ++j)
{
if (s.charAt(j) == '0')
cs++;
else
break;
}
// Count 0s present at the end
for(int j = i + n - 1; j >= i; --j)
{
if (s.charAt(j) == '0')
ce++;
else
break;
}
// Calculate the sum
int val = cs + ce;
// Update the overall
// maximum sum
mx = Math.max(val, mx);
}
// Print the result
System.out.print(mx);
}
// Driver Code
public static void main(String[] args)
{
// Given string
String s = "1001";
// Store the size of the string
int n = s.length();
findMaximumZeros(s, n);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to find the maximum sum of # consecutive 0s present at the start # and end of a string present in any # of the rotations of the given string def findMaximumZeros(st, n): # Check if all the characters # in the string are 0 c0 = 0 # Iterate over characters # of the string for i in range(n): if (st[i] == '0'): c0 += 1 # If the frequency of '1' is 0 if (c0 == n): # Print n as the result print(n) return # Concatenate the string # with itself s = st + st # Stores the required result mx = 0 # Generate all rotations of the string for i in range(n): # Store the number of consecutive 0s # at the start and end of the string cs = 0 ce = 0 # Count 0s present at the start for j in range(i, i + n): if (s[j] == '0'): cs += 1 else: break # Count 0s present at the end for j in range(i + n - 1, i - 1, -1): if (s[j] == '0'): ce += 1 else: break # Calculate the sum val = cs + ce # Update the overall # maximum sum mx = max(val, mx) # Print the result print(mx) # Driver Code if __name__ == "__main__": # Given string s = "1001" # Store the size of the string n = len(s) findMaximumZeros(s, n) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of a string present in any
// of the rotations of the given string
static void findMaximumZeros(string str, int n)
{
// Check if all the characters
// in the string are 0
int c0 = 0;
// Iterate over characters
// of the string
for(int i = 0; i < n; ++i)
{
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n)
{
// Print n as the result
Console.Write(n);
return;
}
// Concatenate the string
// with itself
string s = str + str;
// Stores the required result
int mx = 0;
// Generate all rotations of the string
for(int i = 0; i < n; ++i)
{
// Store the number of consecutive 0s
// at the start and end of the string
int cs = 0;
int ce = 0;
// Count 0s present at the start
for(int j = i; j < i + n; ++j)
{
if (s[j] == '0')
cs++;
else
break;
}
// Count 0s present at the end
for(int j = i + n - 1; j >= i; --j)
{
if (s[j] == '0')
ce++;
else
break;
}
// Calculate the sum
int val = cs + ce;
// Update the overall
// maximum sum
mx = Math.Max(val, mx);
}
// Print the result
Console.Write(mx);
}
// Driver Code
public static void Main(string[] args)
{
// Given string
string s = "1001";
// Store the size of the string
int n = s.Length;
findMaximumZeros(s, n);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of a string present in any
// of the rotations of the given string
function findMaximumZeros(str, n)
{
// Check if all the characters
// in the string are 0
var c0 = 0;
var i;
// Iterate over characters
// of the string
for (i = 0; i < n; ++i) {
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n) {
// Print n as the result
document.write(n);
return;
}
// Concatenate the string
// with itself
var s = str + str;
// Stores the required result
var mx = 0;
var j;
// Generate all rotations of the string
for (i = 0; i < n; ++i) {
// Store the number of consecutive 0s
// at the start and end of the string
var cs = 0;
var ce = 0;
// Count 0s present at the start
for (j = i; j < i + n; ++j) {
if (s[j] == '0')
cs++;
else
break;
}
// Count 0s present at the end
for (j = i + n - 1; j >= i; --j) {
if (s[j] == '0')
ce++;
else
break;
}
// Calculate the sum
var val = cs + ce;
// Update the overall
// maximum sum
mx = Math.max(val, mx);
}
// Print the result
document.write(mx);
}
// Driver Code
// Given string
var s = "1001";
// Store the size of the string
var n = s.length;
findMaximumZeros(s, n);
</script>
Producción:
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es encontrar el número máximo de ceros consecutivos en la string dada . Además, encuentre la suma de 0 s consecutivos al principio y al final de la string, y luego imprima el máximo de ellos.
Siga los pasos a continuación para resolver el problema:
- Compruebe si la frecuencia de ‘1’ en la string, S es igual a 0 o no. Si es cierto, imprima el valor de N como resultado.
- De lo contrario, realice los siguientes pasos:
- Almacene el número máximo de 0s consecutivos en la string dada en una variable, digamos X .
- Inicialice dos variables, comience como 0 y finalice como N-1 .
- Incrementa el valor de cnt y empieza por 1 mientras que S[start] no es igual a ‘ 1 ‘.
- Incrementa el valor de cnt y decrementa end en 1 mientras que S[end] no es igual a ‘ 1 ‘.
- Imprime el máximo de X y cnt 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 maximum sum of
// consecutive 0s present at the start
// and end of any rotation of the string str
void findMaximumZeros(string str, int n)
{
// Stores the count of 0s
int c0 = 0;
for (int i = 0; i < n; ++i) {
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n) {
// Print n as the result
cout << n;
return;
}
// Stores the required sum
int mx = 0;
// Find the maximum consecutive
// length of 0s present in the string
int cnt = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '0')
cnt++;
else {
mx = max(mx, cnt);
cnt = 0;
}
}
// Update the overall maximum sum
mx = max(mx, cnt);
// Find the number of 0s present at
// the start and end of the string
int start = 0, end = n - 1;
cnt = 0;
// Update the count of 0s at the start
while (str[start] != '1' && start < n) {
cnt++;
start++;
}
// Update the count of 0s at the end
while (str[end] != '1' && end >= 0) {
cnt++;
end--;
}
// Update the maximum sum
mx = max(mx, cnt);
// Print the result
cout << mx;
}
// Driver Code
int main()
{
// Given string
string s = "1001";
// Store the size of the string
int n = s.size();
findMaximumZeros(s, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of any rotation of the string str
static void findMaximumZeros(String str, int n)
{
// Stores the count of 0s
int c0 = 0;
for(int i = 0; i < n; ++i)
{
if (str.charAt(i) == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n)
{
// Print n as the result
System.out.print(n);
return;
}
// Stores the required sum
int mx = 0;
// Find the maximum consecutive
// length of 0s present in the string
int cnt = 0;
for(int i = 0; i < n; i++)
{
if (str.charAt(i) == '0')
cnt++;
else
{
mx = Math.max(mx, cnt);
cnt = 0;
}
}
// Update the overall maximum sum
mx = Math.max(mx, cnt);
// Find the number of 0s present at
// the start and end of the string
int start = 0, end = n - 1;
cnt = 0;
// Update the count of 0s at the start
while (str.charAt(start) != '1' && start < n)
{
cnt++;
start++;
}
// Update the count of 0s at the end
while (str.charAt(end) != '1' && end >= 0)
{
cnt++;
end--;
}
// Update the maximum sum
mx = Math.max(mx, cnt);
// Print the result
System.out.println(mx);
}
// Driver Code
public static void main (String[] args)
{
// Given string
String s = "1001";
// Store the size of the string
int n = s.length();
findMaximumZeros(s, n);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find the maximum sum of # consecutive 0s present at the start # and end of any rotation of the string str def findMaximumZeros(string, n): # Stores the count of 0s c0 = 0 for i in range(n): if (string[i] == '0'): c0 += 1 # If the frequency of '1' is 0 if (c0 == n): # Print n as the result print(n, end = "") return # Stores the required sum mx = 0 # Find the maximum consecutive # length of 0s present in the string cnt = 0 for i in range(n): if (string[i] == '0'): cnt += 1 else: mx = max(mx, cnt) cnt = 0 # Update the overall maximum sum mx = max(mx, cnt) # Find the number of 0s present at # the start and end of the string start = 0 end = n - 1 cnt = 0 # Update the count of 0s at the start while (string[start] != '1' and start < n): cnt += 1 start += 1 # Update the count of 0s at the end while (string[end] != '1' and end >= 0): cnt += 1 end -= 1 # Update the maximum sum mx = max(mx, cnt) # Print the result print(mx, end = "") # Driver Code if __name__ == "__main__": # Given string s = "1001" # Store the size of the string n = len(s) findMaximumZeros(s, n) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of any rotation of the string str
static void findMaximumZeros(string str, int n)
{
// Stores the count of 0s
int c0 = 0;
for(int i = 0; i < n; ++i)
{
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n)
{
// Print n as the result
Console.Write(n);
return;
}
// Stores the required sum
int mx = 0;
// Find the maximum consecutive
// length of 0s present in the string
int cnt = 0;
for(int i = 0; i < n; i++)
{
if (str[i] == '0')
cnt++;
else
{
mx = Math.Max(mx, cnt);
cnt = 0;
}
}
// Update the overall maximum sum
mx = Math.Max(mx, cnt);
// Find the number of 0s present at
// the start and end of the string
int start = 0, end = n - 1;
cnt = 0;
// Update the count of 0s at the start
while (str[start] != '1' && start < n)
{
cnt++;
start++;
}
// Update the count of 0s at the end
while (str[end] != '1' && end >= 0)
{
cnt++;
end--;
}
// Update the maximum sum
mx = Math.Max(mx, cnt);
// Print the result
Console.Write(mx);
}
// Driver Code
static public void Main ()
{
// Given string
string s = "1001";
// Store the size of the string
int n = s.Length;
findMaximumZeros(s, n);
}
}
// This code is contributed by avijitmondal1998
Javascript
<script>
//Javascript program for
//the above approach
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of any rotation of the string str
function findMaximumZeros(str, n)
{
// Stores the count of 0s
var c0 = 0;
for (var i = 0; i < n; ++i) {
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n) {
// Print n as the result
document.write( n);
return;
}
// Stores the required sum
var mx = 0;
// Find the maximum consecutive
// length of 0s present in the string
var cnt = 0;
for (var i = 0; i < n; i++) {
if (str[i] == '0')
cnt++;
else {
mx = Math.max(mx, cnt);
cnt = 0;
}
}
// Update the overall maximum sum
mx = Math.max(mx, cnt);
// Find the number of 0s present at
// the start and end of the string
var start = 0, end = n - 1;
cnt = 0;
// Update the count of 0s at the start
while (str[start] != '1' && start < n) {
cnt++;
start++;
}
// Update the count of 0s at the end
while (str[end] != '1' && end >= 0) {
cnt++;
end--;
}
// Update the maximum sum
mx = Math.max(mx, cnt);
// Print the result
document.write( mx);
}
var s = "1001";
// Store the size of the string
var n = s.length;
findMaximumZeros(s, n);
// This code is contributed by SoumikMondal
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por tmprofessor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA