Dada una string binaria S de tamaño N y un entero positivo K , la tarea es modificar repetidamente la string K dada varias veces cambiando todos los 0 que tienen diferentes caracteres adyacentes en cada iteración.
Nota: Para el carácter 0 presente en el índice 0 , cambiará a 1 solo cuando el primer carácter de índice sea 1 y si el último carácter de índice es 0 , entonces cambiará a ‘1’ si el penúltimo carácter de índice es ‘1’ .
Ejemplos:
Entrada: S = “01001”, K = 2
Salida: 11111
Explicación:
A continuación se muestra la operación realizada K(= 2) número de veces:|
Operación 1: después de voltear la string en los índices 0, 2, 3, la string se modifica a «11111».
Operación 2: No existe tal volteo posible para la string modificada S = “11111”.
Después de las operaciones anteriores, la string modificada es «11111».Entrada: S = “10010001”, K = 3
Salida: 11111011
Enfoque: El problema dado se puede resolver realizando la operación dada K número de veces y luego imprimiendo la string resultante formada. Siga los pasos a continuación para resolver este problema:
- Iterar sobre el rango [0, K – 1] usando la variable i y realizar los siguientes pasos:
- Recorra la string dada S sobre el rango [0, N – 1] usando la variable j y realice los siguientes pasos:
- Si el carácter en el índice 0 es 0 , reemplace este valor con el valor del primer índice.
- De lo contrario, si el carácter 0 está presente en el último índice, reemplace este valor con el penúltimo carácter de índice.
- De lo contrario, convierta todos los 0 en 1 si los caracteres adyacentes son diferentes.
- Después de los pasos anteriores, si la string sigue siendo la misma antes de la modificación, salga del bucle .
- Recorra la string dada S sobre el rango [0, N – 1] usando la variable j y realice los siguientes pasos:
- Después de completar los pasos anteriores, imprima la string S como la string modificada resultante.
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 modify the given string
// K number of times by flipping 0s
// having different adjacent characters
void convertString(string S, int k)
{
// Size of the string
int n = S.length();
// Stores modified string after
// each iteration
string temp = S;
// Iterate over the range [0 k]
for (int i = 0; i < k; i++) {
// Traverse the string S
for (int j = 0; j < n; j++) {
// If '0' is present at
// 0th index then replace
// it with 1st index
if (j == 0 && S[j] == '0') {
temp[j] = S[j + 1];
}
// If '0' is present at the
// last index then replace
// it with last index - 1
// character
else if (j == n - 1
&& S[j] == '0') {
temp[j] = S[j - 1];
}
// Otherwise, convert 0s
// to 1 if the adjacent
// characters are different
else if (S[j - 1] != S[j + 1]
&& S[j] == '0') {
temp[j] = '1';
}
}
// If during this iteration
// there is no change in the
// string then break this loop
if (S == temp) {
break;
}
// Update the string S
S = temp;
}
// Print the updated string
cout << S;
}
// Driver Code
int main()
{
string S = "10010001";
int K = 1;
convertString(S, K);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to modify the given string
// K number of times by flipping 0s
// having different adjacent characters
public static void convertString(String Str,int k)
{
// Size of the string
int n = Str.length();
// Stores modified string after
// each iteration
char[] S = Str.toCharArray();
char[] temp = Str.toCharArray();
// Iterate over the range [0 k]
for (int i = 0; i < k; i++) {
// Traverse the string S
for (int j = 0; j < n; j++) {
// If '0' is present at
// 0th index then replace
// it with 1st index
if (j == 0 && S[j] == '0') {
temp[j] = S[j + 1];
}
// If '0' is present at the
// last index then replace
// it with last index - 1
// character
else if (j == n - 1 && S[j] == '0') {
temp[j] = S[j - 1];
}
// Otherwise, convert 0s
// to 1 if the adjacent
// characters are different
else if(j<n-1 && j>0)
{
if (S[j - 1] != S[j + 1] && S[j] == '0') {
temp[j] = '1';
}
}
}
// If during this iteration
// there is no change in the
// string then break this loop
if (S == temp) {
break;
}
// Update the string S
S = temp;
}
// Print the updated string
System.out.println(S);
}
// Driver Code
public static void main(String[] args)
{
String S = "10010001";
int K = 1;
convertString(S, K);
}
}
// this code is contributed by aditya942003patil
Python3
# python 3 program for the above approach # Function to modify the given string # K number of times by flipping 0s # having different adjacent characters def convertString(S, k): # Size of the string n = len(S) # Stores modified string after # each iteration temp = S temp = list(temp) # Iterate over the range [0 k] for i in range(k): # Traverse the string S for j in range(n-1): # If '0' is present at # 0th index then replace # it with 1st index if (j == 0 and S[j] == '0'): temp[j] = S[j + 1] # If '0' is present at the # last index then replace # it with last index - 1 # character elif (j == n - 1 and S[j] == '0'): temp[j] = S[j - 1] # Otherwise, convert 0s # to 1 if the adjacent # characters are different elif (S[j - 1] != S[j + 1] and S[j] == '0'): temp[j] = '1' # If during this iteration # there is no change in the # string then break this loop if (S == temp): break temp = ''.join(temp) # Update the string S S = temp # Print the updated string print(S) # Driver Code if __name__ == '__main__': S = "10010001" K = 1 convertString(S, K) # This code s contributed by ipg2016107.
C#
//C# implementation of above approach
using System;
using System.Text;
public class GFG {
static void convertString(string S, int k)
{
// Size of the string
int n = S.Length;
// Stores modified string after
// each iteration
StringBuilder temp = new StringBuilder(S);
// Iterate over the range [0 k]
for (int i = 0; i < k; i++) {
// Traverse the string S
for (int j = 0; j < n; j++) {
// If '0' is present at
// 0th index then replace
// it with 1st index
if (j == 0 && S[j] == '0') {
temp[j] = S[j + 1];
}
// If '0' is present at the
// last index then replace
// it with last index - 1
// character
else if (j == n - 1 && S[j] == '0') {
temp[j] = S[j - 1];
}
// Otherwise, convert 0s
// to 1 if the adjacent
// characters are different
else if (j>0 && j<n-1 && S[j - 1] != S[j + 1] && S[j] == '0') {
temp[j] = '1';
}
}
// If during this iteration
// there is no change in the
// string then break this loop
string t = temp.ToString();
if (S == t) {
break;
}
// Update the string S
S = t;
}
// Print the updated string
Console.Write(S);
}
// Driver program to test above
public static void Main()
{
string S = "10010001";
int K = 1;
convertString(S, K);
}
}
// This code is contributed by aditya942003patil
Javascript
<script>
// JavaScript program for the above approach
// Function to modify the given string
// K number of times by flipping 0s
// having different adjacent characters
function convertString(S, k)
{
// Size of the string
let n = S.length;
// Stores modified string after
// each iteration
let temp = S;
// Iterate over the range [0 k]
for (let i = 0; i < k; i++) {
// Traverse the string S
for (let j = 0; j < n; j++) {
// If '0' is present at
// 0th index then replace
// it with 1st index
if (j == 0 && S[j] == '0') {
temp[j] = S[j + 1];
}
// If '0' is present at the
// last index then replace
// it with last index - 1
// character
else if (j == n - 1
&& S[j] == '0') {
temp[j] = S[j - 1];
}
// Otherwise, convert 0s
// to 1 if the adjacent
// characters are different
else if (S[j - 1] != S[j + 1]
&& S[j] == '0') {
temp = temp.substring(0,j)+'1'+temp.substring(j+1);
}
}
// If during this iteration
// there is no change in the
// string then break this loop
if (S == temp) {
break;
}
// Update the string S
S = temp;
}
// Print the updated string
document.write(S);
}
// Driver Code
let S = "10010001";
let K = 1;
convertString(S, K);
// This code is contributed by shinjanpatra
</script>
Salida: 11111011
Complejidad temporal: O(N*K)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sharathmajjigi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA