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>
Producción:
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