Una string binaria S de longitud N se construye a partir de una string P de N caracteres y un entero X. La elección del i-ésimo carácter de S es la siguiente:
- Si el carácter P i- X existe y es igual a 1, entonces S i es 1
- si el carácter P i+ X existe y es igual a 1, entonces S i es 1
- si las dos condiciones antes mencionadas son falsas, entonces Si es 0.
Dada la string resultante S y el entero X , reconstruya la string original P. Si ninguna string P puede producir la string S , genera -1.
Ejemplos:
Entrada : S = “10011”, X = 2
Salida : “01100”
Explicación : La string de entrada S = “10011” se puede construir a partir de la string de salida P = “01100”.Entrada : S = “11101100111”, X = 3
Salida : -1
Explicación : La string de entrada S = “11101100111” no se puede construir a partir de ninguna string de salida P.
Enfoque: la tarea se puede resolver tomando una string auxiliar con todos 1s . Siga los pasos a continuación para resolver el problema:
- Inicialice la string P con todos los caracteres como ‘1’.
- Ahora recorra la string S usando un bucle y coloque ceros en las posiciones correctas en P de acuerdo con las condiciones dadas:
- Si S [i] es igual a ‘0’ y P [i- X ] existe, i, e, (i- X )>=0, entonces ponga P [i- X ] = ‘0’.
- Si S [i] es igual a ‘0’ y P [i+ X ] existe, es decir, (i+ X )< N , entonces ponga P [i+ X ] = ‘0’.
- Inicialice una bandera variable = 1 para determinar si la string P existe o no.
- Para verificar la exactitud de la string P construida , recorra la string S usando un bucle for:
- Si S [i]==’1′ y P [i- X ] o P [i+ X ] existe y es igual a ‘1’, entonces la string P es correcta hasta ahora y el recorrido puede continuar.
- Si S [i]==’1′ y P [i- X ] o P [i+ X ] no existe o no es igual a 1, entonces establezca el indicador = 0, emita -1 y salga del ciclo.
- Si la bandera es igual a 0 después del recorrido de la string S , entonces genera la string original P .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the original string P void findString(string S, int X) { // Stores the size of string S int N = S.size(); // Each character of string // P is set to '1' string P(N, '1'); // Loop to put zeroes at // the correct positions in P for (int i = 0; i < N; ++i) { // If the character is '0' if (S[i] == '0') { // If P[i-X] exists if (i - X >= 0) { // Set P[i-X] to '0' P[i - X] = '0'; } // If P[i+X] exists if (i + X < N) { // Set P[i+X] to '0' P[i + X] = '0'; } } } // Set flag to 1 int flag = 1; // Loop to cross check // if P exists or not for (int i = 0; i < N; ++i) { // If the character is '1' if (S[i] == '1') { // If P[i-X] exists and // is equal to '1' or if // P[i+X] exists and // is equal to '1' if ((i - X >= 0 && P[i - X] == '1') || (i + X < N && P[i + X] == '1')) { continue; } else { // Set flag to 0 flag = 0; // Output -1 cout << -1; // Break from the loop break; } } } // If flag is equal to 1 if (flag == 1) { // Output string P cout << P; } } // Driver Code int main() { // Given input string S = "10011"; int X = 2; // Function Call findString(S, X); return 0; }
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to find the original string P static void findString(String S, int X) { // Stores the size of string S int N = S.length(); // Each character of string // converted to char Array P // is set to '1' char[] P = new char[N]; for (int i = 0; i < N; ++i) { P[i] = '1'; } // Loop to put zeroes at // the correct positions in P for (int i = 0; i < N; ++i) { // If the character is '0' if (S.charAt(i) == '0') { // If P[i-X] exists if (i - X >= 0) { // Set P[i-X] to '0' P[i - X] = '0'; } // If P[i+X] exists if (i + X < N) { // Set P[i+X] to '0' P[i + X] = '0'; } } } // Set flag to 1 int flag = 1; // Loop to cross check // if P exists or not for (int i = 0; i < N; ++i) { // If the character is '1' if (S.charAt(i) == '1') { // If P[i-X] exists and // is equal to '1' or if // P[i+X] exists and // is equal to '1' if ((i - X >= 0 && P[i - X] == '1') || (i + X < N && P[i + X] == '1')) { continue; } else { // Set flag to 0 flag = 0; // Output -1 System.out.print(-1); // Break from the loop break; } } } // If flag is equal to 1 if (flag == 1) { // Output string P String p = new String(P); System.out.print(p); } } // Driver Code public static void main(String args[]) { // Given input String S = "10011"; int X = 2; // Function Call findString(S, X); } } // This code is contributed by Samim Hossain Mondal.
Python3
# Python program for the above approach # Function to find the original string P def findString(S, X): # Stores the size of string S N = len(S) # Each character of string # P is set to '1' P = ['1'] * N # Loop to put zeroes at # the correct positions in P for i in range(N): # If the character is '0' if (S[i] == '0'): # If P[i-X] exists if (i - X >= 0): # Set P[i-X] to '0' P[i - X] = '0'; # If P[i+X] exists if (i + X < N): # Set P[i+X] to '0' P[i + X] = '0'; # Set flag to 1 flag = 1; # Loop to cross check # if P exists or not for i in range(N): # If the character is '1' if (S[i] == '1'): # If P[i-X] exists and # is equal to '1' or if # P[i+X] exists and # is equal to '1' if ((i - X >= 0 and P[i - X] == '1') or (i + X < N and P[i + X] == '1')): continue; else: # Set flag to 0 flag = 0; # Output -1 print(-1); # Break from the loop break; # If flag is equal to 1 if (flag == 1): # Output string P print("".join(P)); # Driver Code # Given input S = "10011"; X = 2; # Function Call findString(S, X); # This code is contributed by gfgking
C#
// C# program for the above approach using System; using System.Collections; class GFG { // Function to find the original string P static void findString(string S, int X) { // Stores the size of string S int N = S.Length; // Each character of string // converted to char Array P // is set to '1' char[] P = new char[N]; for (int i = 0; i < N; ++i) { P[i] = '1'; } // Loop to put zeroes at // the correct positions in P for (int i = 0; i < N; ++i) { // If the character is '0' if (S[i] == '0') { // If P[i-X] exists if (i - X >= 0) { // Set P[i-X] to '0' P[i - X] = '0'; } // If P[i+X] exists if (i + X < N) { // Set P[i+X] to '0' P[i + X] = '0'; } } } // Set flag to 1 int flag = 1; // Loop to cross check // if P exists or not for (int i = 0; i < N; ++i) { // If the character is '1' if (S[i] == '1') { // If P[i-X] exists and // is equal to '1' or if // P[i+X] exists and // is equal to '1' if ((i - X >= 0 && P[i - X] == '1') || (i + X < N && P[i + X] == '1')) { continue; } else { // Set flag to 0 flag = 0; // Output -1 Console.Write(-1); // Break from the loop break; } } } // If flag is equal to 1 if (flag == 1) { // Output string P string p = new string(P); Console.Write(p); } } // Driver Code public static void Main() { // Given input string S = "10011"; int X = 2; // Function Call findString(S, X); } } // This code is contributed by Taranpreet
Javascript
<script> // JavaScript program for the above approach // Function to find the original string P const findString = (S, X) => { // Stores the size of string S let N = S.length; // Each character of string // P is set to '1' let P = new Array(N).fill('1'); // Loop to put zeroes at // the correct positions in P for (let i = 0; i < N; ++i) { // If the character is '0' if (S[i] == '0') { // If P[i-X] exists if (i - X >= 0) { // Set P[i-X] to '0' P[i - X] = '0'; } // If P[i+X] exists if (i + X < N) { // Set P[i+X] to '0' P[i + X] = '0'; } } } // Set flag to 1 let flag = 1; // Loop to cross check // if P exists or not for (let i = 0; i < N; ++i) { // If the character is '1' if (S[i] == '1') { // If P[i-X] exists and // is equal to '1' or if // P[i+X] exists and // is equal to '1' if ((i - X >= 0 && P[i - X] == '1') || (i + X < N && P[i + X] == '1')) { continue; } else { // Set flag to 0 flag = 0; // Output -1 document.write(-1); // Break from the loop break; } } } // If flag is equal to 1 if (flag == 1) { // Output string P document.write(P.join("")); } } // Driver Code // Given input let S = "10011"; let X = 2; // Function Call findString(S, X); // This code is contributed by rakeshsahni </script>
01100
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA