Dada una string binaria de tamaño N y un número entero K , la tarea es realizar K operaciones en la string e imprimir la string final:
- Si el número de operación es impar, invierta la string,
- Si el número de operación es par, entonces complemente la string.
Ejemplos:
Entrada: str = “1011”, K = 2
Salida: 0010
Después del primer paso, la string se invertirá y se convertirá en “1101”.
Después del segundo paso, la string se complementará y se convierte en “0010”.Entrada: str = “1001”, K = 4
Salida: 1001
Después de todas las operaciones, la string permanecerá igual.
Enfoque ingenuo:
recorre todos los pasos K y si el paso actual es impar, realice la operación inversa; de lo contrario, complemente la string.
Enfoque eficiente: al observar el patrón de operación dado:
- Si una string se invierte un número par de veces, se obtiene la string original.
- De manera similar, si una string se complementa un número par de veces, se obtiene la string original.
- Por lo tanto, estas operaciones dependen solo de la paridad de K .
- Entonces contaremos el número de operaciones inversas a realizar. Si la paridad es impar , la invertiremos. De lo contrario, la string permanecerá sin cambios.
- De igual forma contaremos el número de operaciones de complemento a realizar. Si la paridad es impar , la complementaremos. De lo contrario, la string permanecerá sin cambios.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to perform K operations upon
// the string and find the modified string
#include <bits/stdc++.h>
using namespace std;
// Function to perform K operations upon
// the string and find modified string
string ReverseComplement(
string s, int n, int k)
{
// Number of reverse operations
int rev = (k + 1) / 2;
// Number of complement operations
int complement = k - rev;
// If rev is odd parity
if (rev % 2)
reverse(s.begin(), s.end());
// If complement is odd parity
if (complement % 2) {
for (int i = 0; i < n; i++) {
// Complementing each position
if (s[i] == '0')
s[i] = '1';
else
s[i] = '0';
}
}
// Return the modified string
return s;
}
// Driver Code
int main()
{
string str = "10011";
int k = 5;
int n = str.size();
// Function call
cout << ReverseComplement(str, n, k);
return 0;
}
Java
// Java program to perform K operations upon
// the String and find the modified String
class GFG{
// Function to perform K operations upon
// the String and find modified String
static String ReverseComplement(
char []s, int n, int k)
{
// Number of reverse operations
int rev = (k + 1) / 2;
// Number of complement operations
int complement = k - rev;
// If rev is odd parity
if (rev % 2 == 1)
s = reverse(s);
// If complement is odd parity
if (complement % 2 == 1) {
for (int i = 0; i < n; i++) {
// Complementing each position
if (s[i] == '0')
s[i] = '1';
else
s[i] = '0';
}
}
// Return the modified String
return String.valueOf(s);
}
static char[] reverse(char a[]) {
int i, n = a.length;
char t;
for (i = 0; i < n / 2; i++) {
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void main(String[] args)
{
String str = "10011";
int k = 5;
int n = str.length();
// Function call
System.out.print(ReverseComplement(str.toCharArray(), n, k));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to perform K operations upon # the string and find the modified string # Function to perform K operations upon # the string and find modified string def ReverseComplement(s,n,k): # Number of reverse operations rev = (k + 1) // 2 # Number of complement operations complement = k - rev # If rev is odd parity if (rev % 2): s = s[::-1] # If complement is odd parity if (complement % 2): for i in range(n): # Complementing each position if (s[i] == '0'): s[i] = '1' else: s[i] = '0' # Return the modified string return s # Driver Code if __name__ == '__main__': str1 = "10011" k = 5 n = len(str1) # Function call print(ReverseComplement(str1, n, k)) # This code is contributed by Surendra_Gangwar
C#
// C# program to perform K operations upon
// the String and find the modified String
using System;
class GFG{
// Function to perform K operations upon
// the String and find modified String
static string ReverseComplement(char []s,
int n, int k)
{
// Number of reverse operations
int rev = (k + 1) / 2;
// Number of complement operations
int complement = k - rev;
// If rev is odd parity
if (rev % 2 == 1)
s = reverse(s);
// If complement is odd parity
if (complement % 2 == 1)
{
for (int i = 0; i < n; i++)
{
// Complementing each position
if (s[i] == '0')
s[i] = '1';
else
s[i] = '0';
}
}
// Return the modified String
return (new string(s));
}
static char[] reverse(char[] a)
{
int i, n = a.Length;
char t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void Main()
{
string str = "10011";
int k = 5;
int n = str.Length;
// Function call
Console.Write(ReverseComplement(str.ToCharArray(), n, k));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to perform K operations upon
// the string and find the modified string
// Function to perform K operations upon
// the string and find modified string
function ReverseComplement( s, n, k)
{
// Number of reverse operations
var rev = parseInt((k + 1) / 2);
// Number of complement operations
var complement = k - rev;
// If rev is odd parity
if (rev % 2)
{
s = s.split('').reverse().join('');
}
// If complement is odd parity
if (complement % 2) {
for (var i = 0; i < n; i++)
{
// Complementing each position
if (s[i] == '0')
s[i] = '1';
else
s[i] = '0';
}
}
// Return the modified string
return s;
}
// Driver Code
var str = "10011";
var k = 5;
var n = str.length;
// Function call
document.write( ReverseComplement(str, n, k));
// This code is contributed by famously.
</script>
Producción:
11001
Complejidad de tiempo: O(N)