Dadas dos strings binarias L y R , la tarea es encontrar el xor de L a R . La longitud de la string binaria es < = 10e6 .
Ejemplos:
Entrada: L = 10, R = 100
Salida: 101
Explicación: L = 2 y R = 4 en sistema decimal. Por lo tanto, el xor será 2^3^4 = 5(101).Entrada: L = 10, R = 10000
Salida: 10001
Enfoque ingenuo: el enfoque más simple para resolver el problema es encontrar todas las strings binarias en el rango [L, R] y luego realizar la operación XOR en todas las strings binarias.
Complejidad de tiempo: (R – L +1) *(N) donde N es la longitud de la string binaria R.
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar aún más al observar que:
- (L ^ (L+1) ^……^(R – 1) ^ R) se puede escribir como (1^2^3 ^…. ^(R-1)^R) ^ (1^2^3 … .. ^(L-2) ^ (L-1)) donde ‘^’ denota la xor bit a bit de los elementos. Entonces el problema se reduce a encontrar el xor de 1 a n .
- Para calcular xor de 1 a n , encuentre el resto de n modulándolo con 4 y guárdelo en una variable, digamos rem y hay cuatro valores posibles de rem :
- Si rem = 0 entonces xor = n .
- Si rem = 1 entonces xor = 1 .
- Si rem = 2 entonces xor = n+1 .
- Si rem = 3 entonces xor = 0 .
Después de observar los puntos anteriores, siga los pasos a continuación para resolver el problema:
- Cree una función sub que reste 1 de una string binaria S de tamaño N realizando los pasos que se mencionan a continuación:
- Iterar en el rango [N-1, 0] usando la variable i y realizar los siguientes pasos:
- Si S[i] = ‘0’ , modifique el valor de S[i] como 1.
- Si S[i] = ‘1’ , modifique el valor de S[i] como 0 y finalice el bucle.
- Devuelve la string S como respuesta.
- Iterar en el rango [N-1, 0] usando la variable i y realizar los siguientes pasos:
- Cree un anuncio de función que agregue 1 a una string binaria S de tamaño N siguiendo los pasos que se mencionan a continuación:
- Inicialice una variable, digamos llevar como 0 .
- Iterar en el rango [N-1, 0] usando la variable i y realizar los siguientes pasos:
- Si S[i] = ‘1’ , modifique el valor de S[i] como 0 y modifique el valor de carry como 1 .
- Si S[i] = ‘0’ , entonces modifique el valor de S[i] como 1 y modifique el valor de carry como 0 y finalice el ciclo.
- Si lleva = 1 , modifique el valor de S como ‘1’ + S y devuelva la string S.
- Cree una función Xor_Finder que devuelva el valor de XOR de 1 a S realizando los pasos que se mencionan a continuación:
- Inicialice una variable, diga val y actualice el valor como S[n] + S[n-1]*2 donde n es la longitud de la string S.
- Ahora, si val = 0 , devuelve la string S como respuesta.
- Si val = 1 , devuelva ‘1’ como respuesta.
- Si val = 2 , devuelve ad(S) como respuesta.
- Si val = 3 , devuelve 0 como respuesta.
- Cree una función final_xor que calcule xor de dos strings binarias L y R realizando los pasos que se mencionan a continuación:
- Agregue el carácter ‘0’ a la string L mientras que L.size() != R.size() .
- Inicialice una string, digamos ans , que almacenará el valor de xor de las strings binarias L y R.
- Iterar en el rango [0, R.size()-1] usando la variable i y realizar los siguientes pasos:
- Si L[i] = R[i] , agregue el carácter ‘0’ al final de la string ans.
- Si L[i] != R[i] , agregue el carácter ‘1’ al final de la string ans.
- Devuelve string ans como el xor de las dos strings.
- Cree una función xorr para calcular xor de L a R realizando los siguientes pasos:
- Modifique el valor de L como sub(L) .
- Modifique el valor de L y R llamando a la función xor_finder(L) y xor_finder(R) para calcular xor de 1 a L y de 1 a R respectivamente.
- Inicialice una variable, diga ans y actualice el valor de ans actualizando el valor como final_xor(L, R) .
- Devuelve la string ans como respuesta.
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 subtract one
// from the binary string
string sub(string s)
{
int n = s.size();
for (int i = n - 1; i >= 0; i--) {
// If the current character
// is 0 change it to 1
if (s[i] == '0') {
s[i] = '1';
}
else {
// If the character is 1
// Change is to 0 and
// terminate the loop
s[i] = '0';
break;
}
}
// Return the answer
return s;
}
// Function to add 1 in the
// binary string
string ad(string s)
{
int n = s.size();
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
// If s[i]=='1' it
// will change s[i] to 0
// and carry = 1
if (s[i] == '1') {
carry = 1;
s[i] = '0';
}
else {
// If s[i]=='0' it
// will change s[i] to 1
// and carry = 0 and
// end the loop
carry = 0;
s[i] = '1';
break;
}
}
// If still carry left
// append character 1 to the
// beginning of the string
if (carry) {
s = '1' + s;
}
return s;
}
// Function to find xor from 1 to n
string xor_finder(string s)
{
int n = s.size() - 1;
// Variable val stores the
// remainder when binary string
// is divided by 4
int val = s[n] - '0';
val = val + (s[n - 1] - '0') * 2;
// If val == 0 the xor from
// 1 to n will be n itself
if (val == 0) {
return s;
}
else if (val == 1) {
// If val == the xor from
// 1 to n will be 1 itself
s = '1';
return s;
}
else if (val == 2) {
// If val == 2 the xor from
// 1 to n will be n+1 itself
return (ad(s));
}
else if (val == 3) {
// If val == 3 the xor from
// 1 to n will be 0 itself
s = '0';
return s;
}
}
// Function to find the xor of two
// binary string
string final_xor(string L, string R)
{
// Using loop to equalise the size
// of string L and R
while (L.size() != R.size()) {
L = '0' + L;
}
string ans = "";
for (int i = 0; i < L.size(); i++) {
// If ith bit of L is 0 and
// ith bit of R is 0
// then xor will be 0
if (L[i] == '0' && R[i] == '0') {
ans += '0';
}
else if (L[i] == '0' && R[i] == '1'
|| L[i] == '1' && R[i] == '0') {
// If ith bit of L is 0 and
// ith bit of R is 1 or
// vice versa then xor will be 1
ans += '1';
}
else {
// If ith bit of L is 1 and
// ith bit of R is 1
// then xor will be 0
ans += '0';
}
}
return ans;
}
// Function to find xor from L to R
string xorr(string L, string R)
{
// changing L to L - 1
L = sub(L);
// Finding xor from 1 to L - 1
L = xor_finder(L);
// Finding xor from 1 to R
R = xor_finder(R);
// Xor of 1, 2, ..., L-1 and 1, 2, ...., R
string ans = final_xor(L, R);
return ans;
}
// Driver Code
int main()
{
// Given Input
string L = "10", R = "10000";
// Function Call
cout << xorr(L, R) << endl;
return 0;
}
Java
// Java program for above approach
class GFG{
// Function to subtract one
// from the binary string
public static String sub(String s)
{
StringBuilder new_s = new StringBuilder(s);
int n = s.length();
for(int i = n - 1; i >= 0; i--)
{
// If the current character
// is 0 change it to 1
if (s.charAt(i) == '0')
{
new_s.setCharAt(i, '1');
}
else
{
// If the character is 1
// Change is to 0 and
// terminate the loop
new_s.setCharAt(i, '0');
break;
}
}
// Return the answer
return new_s.toString();
}
// Function to add 1 in the
// binary string
public static String ad(String s)
{
int n = s.length();
StringBuilder new_s = new StringBuilder(s);
int carry = 0;
for(int i = n - 1; i >= 0; i--)
{
// If s[i]=='1' it
// will change s[i] to 0
// and carry = 1
if (s.charAt(i) == '1')
{
carry = 1;
new_s.setCharAt(i, '0');
}
else
{
// If s[i]=='0' it
// will change s[i] to 1
// and carry = 0 and
// end the loop
carry = 0;
new_s.setCharAt(i, '1');
break;
}
}
// If still carry left
// append character 1 to the
// beginning of the string
if (carry != 0)
{
s = '1' + new_s.toString();
}
return s;
}
// Function to find xor from 1 to n
public static String xor_finder(String s)
{
int n = s.length() - 1;
// Variable val stores the
// remainder when binary string
// is divided by 4
int val = s.charAt(n) - '0';
val = val + (s.charAt(n - 1) - '0') * 2;
// If val == 0 the xor from
// 1 to n will be n itself
if (val == 0)
{
return s;
}
else if (val == 1)
{
// If val == 1 the xor from
// 1 to n will be 1 itself
s = "1";
return s;
}
else if (val == 2)
{
// If val == 2 the xor from
// 1 to n will be n+1 itself
return (ad(s));
}
else
{
// If val == 3 the xor from
// 1 to n will be 0 itself
s = "0";
return s;
}
}
// Function to find the xor of two
// binary string
public static String final_xor(String L, String R)
{
// Using loop to equalise the size
// of string L and R
while (L.length() != R.length())
{
L = '0' + L;
}
String ans = "";
for(int i = 0; i < L.length(); i++)
{
// If ith bit of L is 0 and
// ith bit of R is 0
// then xor will be 0
if (L.charAt(i) == '0' && R.charAt(i) == '0')
{
ans += '0';
}
else if (L.charAt(i) == '0' && R.charAt(i) == '1' ||
L.charAt(i) == '1' && R.charAt(i) == '0')
{
// If ith bit of L is 0 and
// ith bit of R is 1 or
// vice versa then xor will be 1
ans += '1';
}
else
{
// If ith bit of L is 1 and
// ith bit of R is 1
// then xor will be 0
ans += '0';
}
}
return ans;
}
// Function to find xor from L to R
public static String xorr(String L, String R)
{
// Changing L to L - 1
L = sub(L);
// Finding xor from 1 to L - 1
L = xor_finder(L);
// Finding xor from 1 to R
R = xor_finder(R);
// Xor of 1, 2, ..., L-1 and 1, 2, ...., R
String ans = final_xor(L, R);
return ans;
}
// Driver code
public static void main(String[] args)
{
// Given Input
String L = "10", R = "10000";
// Function Call
System.out.println(xorr(L, R));
}
}
// This code is contributed by garry133
Python3
# Python program for the above approach # Function to subtract one # from the binary string def sub(s): # Changing string into list to change # the characters in O(1) s = list(s) n = len(s) for i in range(n-1, -1, -1): # If the current character # is 0 change it to 1 if (s[i] == '0'): s[i] = '1' else: # If the character is 1 # Change is to 0 and # terminate the loop s[i] = '0' break # Return the answer # converting list to string s = "".join(s) return s # Function to add 1 in the # binary string def ad(s): n = len(s) carry = 0 for i in range(n-1, -1, -1): # If s[i]=='1' it # will change s[i] to 0 # and carry = 1 if (s[i] == '1'): carry = 1 s[i] = '0' else: # If s[i]=='0' it # will change s[i] to 1 # and carry = 0 and # end the loop carry = 0 s[i] = '1' break # If still carry left # append character 1 to the # beginning of the string if (carry): s = '1' + s return s # Function to find xor from 1 to n def xor_finder(s): n = len(s) - 1 # Variable val stores the # remainder when binary string # is divided by 4 val = ord(s[n]) - 48 val = val + (ord(s[n - 1]) - 48) * 2 # If val == 0 the xor from # 1 to n will be n itself if (val == 0): return s else if (val == 1): # If val == the xor from # 1 to n will be 1 itself s = '1' return s else if (val == 2): # If val == 2 the xor from # 1 to n will be n+1 itself return (ad(s)) else if (val == 3): # If val == 3 the xor from # 1 to n will be 0 itself s = '0' return s # Function to find the xor of two # binary string def final_xor(L, R): # Using loop to equalise the size # of string L and R while (len(L) != len(R)): L = '0' + L ans = "" for i in range(len(L)): # If ith bit of L is 0 and # ith bit of R is 0 # then xor will be 0 if (L[i] == '0' and R[i] == '0'): ans += '0' else if (L[i] == '0' and R[i] == '1' or L[i] == '1' and R[i] == '0'): # If ith bit of L is 0 and # ith bit of R is 1 or # vice versa then xor will be 1 ans += '1' else: # If ith bit of L is 1 and # ith bit of R is 1 # then xor will be 0 ans += '0' return ans # Function to find xor from L to R def xorr(L, R): # changing L to L - 1 L = sub(L) # Finding xor from 1 to L - 1 L = xor_finder(L) # Finding xor from 1 to R R = xor_finder(R) # Xor of 1, 2, ..., L-1 and 1, 2, ...., R ans = final_xor(L, R) return ans # Driver Code # Given Input L = "10" R = "10000" # Function Call print(xorr(L, R)) # This code is contributed by rj13to.
Producción:
10001
Complejidad de tiempo: O(N) donde N es la longitud de la string
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aayushstar300 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA