Dada una string binaria str[] de tamaño N y un entero M . Esta string binaria se puede modificar cambiando todos los 0 a 1 que tienen exactamente un 1 como vecino. La tarea es encontrar el estado final de la string binaria después de M iteraciones de este tipo.
Nota: 2≤N≤10 3 , 1≤M≤10 9
Ejemplos:
Entrada: str=”01100″, M=1
Salida: 11110
Explicación: Después de la primera iteración: 11110Entrada: str = “0110100”, M=3
Salida: 1110111
Explicación: después de la primera iteración: 1110110, después de la segunda iteración: 1110111, después de la tercera iteración: permanece igual.
Enfoque: La solución se basa en la observación de que la modificación puede continuar por no más de N iteraciones, porque incluso si en cada iteración, al menos se voltea un 0 , entonces continuaría por un máximo de N veces y, si no hay cero volteado en una iteración, esto significaría que la string binaria permanece en el mismo estado que en el paso anterior y la simulación ha terminado. Por lo tanto, el número total de iteraciones será como mínimo N y M. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable N y establezca su valor en la longitud de la string binaria str .
- Establezca el valor de M al mínimo de N o M.
- Iterar en el ciclo while externo hasta que M sea mayor que 0.
- Inicialice la string s1=”” para almacenar la versión modificada después de la iteración actual.
- Iterar en el bucle for interno de i=0 a i<N.
- Compruebe el carácter en el i-ésimo índice de la string binaria dada str[].
- Si str[i]==’1′, agregue este carácter a la string binaria s1.
- De lo contrario, verifique los caracteres adyacentes en los índices i-1 e i+1.
- Si hay exactamente un 1 , agregue 1 a la string binaria s1.
- De lo contrario, agregue 0 a la string binaria s1.
- Después del ciclo interno, verifique si las strings binarias str y s1 son iguales o no.
- En caso afirmativo, rompa el bucle exterior.
- De lo contrario, establezca la string binaria s1 como el nuevo valor de la string binaria str y reduzca el valor de M en 1.
- Finalmente, imprima la string binaria s1.
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 modified
// binary string after M iterations
void findString(string str, int M)
{
int N = str.length();
// Set the value of M to the minimum
// of N or M.
M = min(M, N);
// Declaration of current string state
string s1 = "";
// Loop over M iterations
while (M != 0) {
// Set the current state as null
// before each iteration
s1 = "";
for (int i = 0; i < N; i++) {
if (str[i] == '0') {
// Check if this zero has exactly
// one 1 as neighbour
if ((str[i - 1] == '1'
&& str[i + 1] != '1')
|| (str[i - 1] != '1'
&& str[i + 1] == '1'))
// Flip the zero
s1 += '1';
else
s1 += '0';
}
else
s1 += '1';
}
// If there is no change,
// then no need for
// further iterations.
if (str == s1)
break;
// Set the current state
// as the new previous state
str = s1;
M--;
}
cout << s1;
}
// Driver Code
int main()
{
// Given String
string str = "0110100";
// Number of Iterations
int M = 3;
// Function Call
findString(str, M);
return 0;
}
Java
// Java program for the above approach.
import java.io.*;
import static java.lang.Math.min;
import java.lang.*;
class GFG
{
// Function to find the modified
// binary string after M iterations
public static void findString(String str, int M)
{
int N = str.length();
// Set the value of M to the minimum
// of N or M.
M = Math.min(M, N);
// Declaration of current string state
String s1 = "";
// Loop over M iterations
while (M != 0) {
// Set the current state as null
// before each iteration
s1 = "";
for (int i = 0; i < N; i++) {
if (str.charAt(i) == '0') {
// Check if this zero has exactly
// one 1 as neighbour
if ((str.charAt(i) == '1'
&& str.charAt(i) != '1')
|| (str.charAt(i) == '1'
&& str.charAt(i) == '1'))
// Flip the zero
s1 += '1';
else
s1 += '0';
}
else
s1 += '1';
}
// If there is no change,
// then no need for
// further iterations.
if (str == s1)
break;
// Set the current state
// as the new previous state
str = s1;
M--;
}
System.out.print(s1);
}
// Driver Code
public static void main (String[] args)
{
// Given String
String str = "0110100";
// Number of Iterations
int M = 3;
// Function Call
findString(str, M);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python 3 program for the above approach. # Function to find the modified # binary string after M iterations def findString(str,M): N = len(str) # Set the value of M to the minimum # of N or M. M = min(M, N) # Declaration of current string state s1 = "" # Loop over M iterations while (M != 0): # Set the current state as null # before each iteration s1 = "" for i in range(N-1): if (str[i] == '0'): # Check if this zero has exactly # one 1 as neighbour if ((str[i - 1] == '1' and str[i + 1] != '1') or (str[i - 1] != '1' and str[i + 1] == '1')): # Flip the zero s1 += '1' else: s1 += '0' else: s1 += '1' # If there is no change, # then no need for # further iterations. if (str == s1): break s1 += '1' # Set the current state # as the new previous state str = s1 M -= 1 print(s1) # Driver Code if __name__ == '__main__': # Given String str = "0110100" # Number of Iterations M = 3 # Function Call findString(str, M) # This code is contributed by ipg2016107.
C#
// C# program for the above approach.
using System;
class GFG {
// Function to find the modified
// binary string after M iterations
static void findString(string str, int M)
{
int N = str.Length;
// Set the value of M to the minimum
// of N or M.
M = Math.Min(M, N);
// Declaration of current string state
string s1 = "";
// Loop over M iterations
while (M != 0) {
// Set the current state as null
// before each iteration
s1 = "";
for (int i = 0; i < N; i++) {
if (str[i] == '0')
{
// Check if this zero has exactly
// one 1 as neighbour
if (((i>0 && str[i - 1] == '1') && (i<N-1 && str[i + 1] != '1')) || ((i>0 && str[i - 1] != '1') && (i<N-1 && str[i + 1] == '1')))
{
// Flip the zero
s1 += '1';
}
else
{
if(i==0 || i==N-1)
{
s1 += '1';
}
else
{
s1 += '0';
}
}
}
else
{
s1 += '1';
}
}
// If there is no change,
// then no need for
// further iterations.
if (str == s1)
break;
// Set the current state
// as the new previous state
//str = s1;
M--;
}
Console.WriteLine(s1);
}
static void Main() {
// Given String
string str = "0110100";
// Number of Iterations
int M = 3;
// Function Call
findString(str, M);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Function to find the modified
// binary let after M iterations
function findlet(str, M)
{
let N = str.length;
// Set the value of M to the minimum
// of N or M.
M = Math.min(M, N);
// Declaration of current let state
let s1 = "";
// Loop over M iterations
while (M != 0) {
// Set the current state as null
// before each iteration
s1 = "";
for (let i = 0; i < N; i++) {
if (str[i] == '0') {
// Check if this zero has exactly
// one 1 as neighbour
if ((str[i - 1] == '1'
&& str[i + 1] != '1')
|| (str[i - 1] != '1'
&& str[i + 1] == '1'))
// Flip the zero
s1 += '1';
else
s1 += '0';
}
else
s1 += '1';
}
// If there is no change,
// then no need for
// further iterations.
if (str == s1)
break;
// Set the current state
// as the new previous state
str = s1;
M--;
}
document.write(s1);
}
// Driver Code
// Given let
let str = "0110100";
// Number of Iterations
let M = 3;
// Function Call
findlet(str, M);
// This code is contributed by splevel62.
</script>
Producción
1110111
Complejidad de tiempo: O(min(M, N)*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dinijain99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA