Encuentre una string binaria convirtiendo todos los 01 o 10 a 11 después de M iteraciones

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: 11110

Entrada: 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:

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

Deja una respuesta

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