Voltee todos los 0 en strings binarias dadas K veces con diferentes vecinos

Posted on by Rudeus Greyrat

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 .
  • 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *