Dada una array entera arr[] de consultas de tamaño N y Q. Cada consulta tiene la forma (L, R) , donde L y R son índices de la array. La tarea es encontrar el valor XOR del subarreglo arr[L…R] .
Ejemplos:
Entrada: arr[] = {2, 5, 1, 6, 1, 2, 5} consulta[] = {{1, 4}}
Salida: 3
El valor XOR de arr[1…4] es 3.Entrada: arr[] = {2, 5, 1, 6, 1, 2, 5} consulta[] = {{0, 6}}
Salida: 6
El valor XOR de arr[0…6] es 6.
Aproximación al espacio auxiliar O(N): Consulte este artículo para obtener información sobre la aproximación al espacio auxiliar O(N).
Enfoque: aquí discutiremos una solución de espacio constante, pero modificaremos la array de entrada.
1. Actualice la array de entrada del índice 1 a N – 1 , de modo que arr[i] almacene el XOR de arr[0] a arr[i] .
array[i] = XOR(array[0], array[1], .., array[i])
2. Para procesar una consulta de L a R simplemente devuelva arr[L-1] ^ arr[R] .
Por ejemplo:
Considere el ejemplo: arr[] = { 3, 2, 4, 5, 1, 1, 5, 3 }, query[] = {{1, 4 }, { 3, 7}}
Después de tomar el XOR de elementos consecutivos , arr[] = {3, 1, 5, 0, 1, 0, 5, 6}
Para la primera consulta {1, 4} ans = arr[0] ^ arr[4] = 3 ^ 1 = 2
Para la segunda consulta {3, 7} respuesta = arr[2] ^ arr[7] = 5 ^ 6 = 3
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find XOR
// in a range from L to R
#include <bits/stdc++.h>
using namespace std;
// Function to find XOR
// in a range from L to R
void find_Xor(int arr[],
pair<int, int> query[],
int N, int Q)
{
// Compute xor from arr[0] to arr[i]
for (int i = 1; i < N; i++) {
arr[i] = arr[i] ^ arr[i - 1];
}
int ans = 0;
// process every query
// in constant time
for (int i = 0; i < Q; i++) {
// if L==0
if (query[i].first == 0)
ans = arr[query[i].second];
else
ans = arr[query[i].first - 1]
^ arr[query[i].second];
cout << ans << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 4, 5,
1, 1, 5, 3 };
int N = 8;
int Q = 2;
pair<int, int> query[Q]
= { { 1, 4 },
{ 3, 7 } };
// query[]
find_Xor(arr, query, N, Q);
return 0;
}
Java
// Java program to find XOR
// in a range from L to R
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find XOR
// in a range from L to R
static void find_Xor(int arr[],
pair query[],
int N, int Q)
{
// Compute xor from arr[0] to arr[i]
for(int i = 1; i < N; i++)
{
arr[i] = arr[i] ^ arr[i - 1];
}
int ans = 0;
// Process every query
// in constant time
for(int i = 0; i < Q; i++)
{
// If L==0
if (query[i].first == 0)
ans = arr[query[i].second];
else
ans = arr[query[i].first - 1] ^
arr[query[i].second];
System.out.print(ans + "\n");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 4, 5,
1, 1, 5, 3 };
int N = 8;
int Q = 2;
pair query[] = { new pair(1, 4),
new pair(3, 7) };
// query[]
find_Xor(arr, query, N, Q);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to find XOR # in a range from L to R # Function to find XOR # in a range from L to R def find_Xor(arr, query, N, Q): # Compute xor from arr[0] to arr[i] for i in range(1, N): arr[i] = arr[i] ^ arr[i - 1] ans = 0 # Process every query # in constant time for i in range(Q): # If L == 0 if query[i][0] == 0: ans = arr[query[i][1]] else: ans = (arr[query[i][0] - 1] ^ arr[query[i][1]]) print(ans) # Driver code def main(): arr = [ 3, 2, 4, 5, 1, 1, 5, 3 ] N = 8 Q = 2 # query[] query = [ [ 1, 4 ], [ 3, 7 ] ] find_Xor(arr, query, N, Q) main() # This code is contributed by Stuti Pathak
C#
// C# program to find XOR
// in a range from L to R
using System;
class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find XOR
// in a range from L to R
static void find_Xor(int []arr,
pair []query,
int N, int Q)
{
// Compute xor from arr[0] to arr[i]
for(int i = 1; i < N; i++)
{
arr[i] = arr[i] ^ arr[i - 1];
}
int ans = 0;
// Process every query
// in constant time
for(int i = 0; i < Q; i++)
{
// If L==0
if (query[i].first == 0)
ans = arr[query[i].second];
else
ans = arr[query[i].first - 1] ^
arr[query[i].second];
Console.Write(ans + "\n");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 2, 4, 5,
1, 1, 5, 3 };
int N = 8;
int Q = 2;
pair []query = { new pair(1, 4),
new pair(3, 7) };
// query[]
find_Xor(arr, query, N, Q);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find XOR
// in a range from L to R
// Function to find XOR
// in a range from L to R
function find_Xor(arr, query, N, Q)
{
// Compute xor from arr[0] to arr[i]
for (var i = 1; i < N; i++) {
arr[i] = arr[i] ^ arr[i - 1];
}
var ans = 0;
// process every query
// in constant time
for (var i = 0; i < Q; i++) {
// if L==0
if (query[i][0] == 0)
ans = arr[query[i][1]];
else
ans = arr[query[i][0] - 1]
^ arr[query[i][1]];
document.write( ans + "<br>");
}
}
// Driver Code
var arr = [3, 2, 4, 5,
1, 1, 5, 3];
var N = 8;
var Q = 2;
var query
= [[1, 4],
[3, 7]];
// query[]
find_Xor(arr, query, N, Q);
</script>
2 3
Complejidad Temporal: O (N + Q)
Espacio Auxiliar: O (1)
Publicación traducida automáticamente
Artículo escrito por SADDAMANSARI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA