Dada una array A de n enteros, digamos A 1 , A 2 , A 3 , …, A n . Se le dan Q consultas de la forma [l, r] . La tarea es encontrar el XOR de los XOR de todos los subarreglos de un arreglo que tiene elementos A l , A l+1 , ….., A r .
Ejemplos:
Input : A[] = { 1, 2, 3, 4, 5 }, Q = 3
q1 = { 1, 2 }
q2 = { 1, 3 }
q3 = { 2, 4 }
Output : 0
2
6
For query 1, the extracted array is [1, 2] and
subarrays of the array is [1], [2], [1, 2].
So, the answer is (1) ⊕ (2) ⊕ (1 ⊕ 2) = 0.
For query 2, the extracted array is [1, 2, 3] and
subarrays of the array is
[1], [2], [1, 2], [2, 3], [1, 2, 3].
So the answer is (1) ⊕ (2) ⊕ (3) ⊕ (1 ⊕ 2) ⊕
(2 ⊕ 3) ⊕ (1 ⊕ 2 ⊕ 3) = 2.
For query 3, the extracted array is [2, 3, 4] and
subarrays of the array is
[2], [3], [4], [2, 3], [3, 4], [2, 3, 4].
So the answer is (2) ⊕ (3) ⊕ (4) ⊕ (2 ⊕ 3) ⊕
(3 ⊕ 4) ⊕ (2 ⊕ 3 ⊕ 4) = 6.
Input : A[] = { 5, 8, 9, 1, 7 }, Q = 3
query1 = { 1, 3 }
query2 = { 3, 4 }
query3 = { 2, 5 }
Output : 12
0
0
En primer lugar recordar las propiedades de XOR,
- x ⊕ x = 0
- Si x ⊕ y = z, entonces x = y ⊕ z
Usando la primera propiedad, podemos decir que cualquier número x XORed un número par de veces dará como resultado un 0 y un número impar de veces dará como resultado x.
Si queremos encontrar XOPR de XOR en todos los subarreglos de un arreglo, necesitamos encontrar los elementos que aparecen un número impar de veces en todos los subarreglos en total.
Digamos que tenemos una array [1, 2, 3]. Sus subarreglos serán [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].
- ha ocurrido tres veces en total.
- ha ocurrido cuatro veces en total.
- ha ocurrido tres veces en total.
Podemos observar que el número en el i -ésimo índice tendrá (i + 1)x(sizeofarray – i) frecuencia.
Si una array tiene un número impar de enteros, a partir del primer elemento, cada elemento alternativo aparecerá un número impar de veces en todos los subarreglos en total. Por lo tanto, el XOR de los XOR de todos los subarreglos será el XOR de los elementos alternativos en los arreglos.
Si una array tiene un número par de enteros, cada elemento aparecerá un número par de veces en todos los subarreglos en total. Por lo tanto, el XOR de los XOR de todos los subarreglos siempre será 0.
Recorrer el arreglo para cada consulta es ineficiente. Podemos almacenar el valor de los XOR en todos los elementos haciéndolo XOR con los elementos alternativos usando recurrencia
prefix_xor[i] = A[i] ⊕ prefix_xor[i – 2]
Para cada consulta, tenemos un índice inicial como l y un índice final como r. Si (r – l + 1) es impar, la respuesta será prefix_xor[r] ⊕ prefix_xor[l – 2].
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to answer queries on XOR of XORs
// of all subarray
#include <bits/stdc++.h>
#define N 100
using namespace std;
// Output for each query
void ansQueries(int prefeven[], int prefodd[],
int l, int r)
{
// If number of element is even.
if ((r - l + 1) % 2 == 0)
cout << "0";
// If number of element is odd.
else {
// if l is even
if (l % 2 == 0)
cout << (prefeven[r] ^ prefeven[l - 1]);
// if l is odd
else
cout << (prefodd[r] ^ prefodd[l - 1]);
}
cout << endl;
}
// Wrapper Function
void wrapper(int arr[], int n, int l[], int r[], int q)
{
int prefodd[N] = { 0 }, prefeven[N] = { 0 };
// Evaluating prefixodd and prefixeven
for (int i = 1; i <= n; i++) {
if ((i) % 2 == 0) {
prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}
else {
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
}
}
int i = 0;
while (i != q) {
ansQueries(prefeven, prefodd, l[i], r[i]);
i++;
}
}
// Driven Program
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int l[] = { 1, 1, 2 };
int r[] = { 2, 3, 4 };
int q = sizeof(l) / sizeof(l[0]);
wrapper(arr, n, l, r, q);
return 0;
}
Java
// JAVA Code for Queries on XOR
// of XORs of all subarrays
import java.util.*;
class GFG {
// Output for each query
static void ansQueries(int prefeven[],
int prefodd[],
int l, int r)
{
// If number of element is even.
if ((r - l + 1) % 2 == 0)
System.out.println("0");
// If number of element is odd.
else
{
// if l is even
if (l % 2 == 0)
System.out.println(prefeven[r] ^
prefeven[l - 1]);
// if l is odd
else
System.out.println(prefodd[r] ^
prefodd[l - 1]);
}
}
// Wrapper Function
static void wrapper(int arr[], int n,
int l[], int r[],
int q)
{
int prefodd[] = new int[100];
int prefeven[] = new int[100];
// Evaluating prefixodd
// and prefixeven
for (int i = 1; i <= n; i++) {
if ((i) % 2 == 0) {
prefeven[i] = arr[i - 1] ^
prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}
else
{
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^
arr[i - 1];
}
}
int i = 0;
while (i != q){
ansQueries(prefeven, prefodd,
l[i], r[i]);
i++;
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4 , 5};
int n = arr.length;
int l[] = {1, 1, 2};
int r[] = {2, 3, 4};
int q = l.length;
wrapper(arr, n, l, r, q);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python 3
# Python 3 Program to answer queries on
# XOR of XORs of all subarray
N = 100
# Output for each query
def ansQueries(prefeven, prefodd, l, r):
# If number of element is even.
if ((r - l + 1) % 2 == 0):
print("0")
# If number of element is odd.
else :
# if l is even
if (l % 2 == 0):
print(prefeven[r] ^
prefeven[l - 1])
# if l is odd
else:
print(prefodd[r] ^
prefodd[l - 1])
# Wrapper Function
def wrapper(arr, n, l, r, q):
prefodd = [0] * N
prefeven = [0] * N
# Evaluating prefixodd and prefixeven
for i in range(1, n + 1) :
if ((i) % 2 == 0) :
prefeven[i] = arr[i - 1] ^ prefeven[i - 1]
prefodd[i] = prefodd[i - 1]
else :
prefeven[i] = prefeven[i - 1]
prefodd[i] = prefodd[i - 1] ^ arr[i - 1]
i = 0
while (i != q) :
ansQueries(prefeven, prefodd, l[i], r[i])
i += 1
# Driver Code
if __name__ == "__main__":
arr = [ 1, 2, 3, 4, 5 ]
n = len(arr)
l = [ 1, 1, 2 ]
r = [ 2, 3, 4 ]
q = len(l)
wrapper(arr, n, l, r, q)
# This code is contributed by ita_c
C#
// C# code for Queries on XOR
// of XORs of all subarrays
using System;
class GFG {
// Output for each query
static void ansQueries(int[] prefeven,
int[] prefodd,
int l, int r)
{
// If number of element is even.
if ((r - l + 1) % 2 == 0)
Console.WriteLine("0");
// If number of element is odd.
else {
// if l is even
if (l % 2 == 0)
Console.WriteLine(prefeven[r] ^ prefeven[l - 1]);
// if l is odd
else
Console.WriteLine(prefodd[r] ^ prefodd[l - 1]);
}
}
// Wrapper Function
static void wrapper(int[] arr, int n,
int[] l, int[] r,
int q)
{
int[] prefodd = new int[100];
int[] prefeven = new int[100];
// Evaluating prefixodd
// and prefixeven
for (int i = 1; i <= n; i++) {
if ((i) % 2 == 0) {
prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}
else {
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
}
}
int j = 0;
while (j != q) {
ansQueries(prefeven, prefodd,
l[j], r[j]);
j++;
}
}
/* Driver program to test above function */
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
int[] l = { 1, 1, 2 };
int[] r = { 2, 3, 4 };
int q = l.Length;
wrapper(arr, n, l, r, q);
}
}
// This code is contributed by vt_m.
PHP
<?php
// php Program to answer
// queries on XOR of XORs
// of all subarray
// Output for each query
function ansQueries($prefeven, $prefodd,
$l, $r)
{
// If number of element is even.
if (($r - $l + 1) % 2 == 0)
{
echo "0";
}
// If number of element is odd.
else {
// if l is even
if ($l % 2 == 0)
echo ($prefeven[$r] ^
$prefeven[$l - 1]);
// if l is odd
else
echo ($prefodd[$r] ^
$prefodd[$l - 1]);
}
echo "\n";
}
// Wrapper Function
function wrapper(array $arr, $n, array $l,
array $r, $q)
{
$prefodd=array_fill(0,100,0);
$prefeven=array_fill(0,100,0);
// Evaluating prefixodd
// and prefixeven
for ($i = 1; $i <= $n; $i++)
{
if (($i) % 2 == 0)
{
$prefeven[$i] = $arr[$i - 1] ^
$prefeven[$i - 1];
$prefodd[$i] = $prefodd[$i - 1];
}
else {
$prefeven[$i] = $prefeven[$i - 1];
$prefodd[$i] = $prefodd[$i - 1] ^
$arr[$i - 1];
}
}
$i = 0;
while ($i != $q) {
ansQueries($prefeven, $prefodd,
$l[$i], $r[$i]);
$i++;
}
}
// Driver code
$arr = array ( 1, 2, 3, 4, 5 );
$n = sizeof($arr) / sizeof($arr[0]);
$l=array ( 1, 1, 2 );
$r=array ( 2, 3, 4 );
$q = sizeof($l) / sizeof($l[0]);
wrapper($arr, $n, $l, $r, $q);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program for Queries on XOR
// of XORs of all subarrays
// Output for each query
function ansQueries(prefeven,
prefodd,
l, r)
{
// If number of element is even.
if ((r - l + 1) % 2 == 0)
document.write("0");
// If number of element is odd.
else
{
// if l is even
if (l % 2 == 0)
document.write(prefeven[r] ^
prefeven[l - 1]) ;
// if l is odd
else
document.write(prefodd[r] ^
prefodd[l - 1] );
}
document.write( "<br/>");
}
// Wrapper Function
function wrapper(arr, n,
l, r, q)
{
let prefodd = [];
let prefeven = [];
// Evaluating prefixodd
// and prefixeven
for (let i = 1; i <= n; i++) {
if ((i) % 2 == 0) {
prefeven[i] = arr[i - 1] ^
prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}
else
{
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^
arr[i - 1];
}
}
let i = 0;
while (i != q){
ansQueries(prefeven, prefodd,
l[i], r[i]);
i++;
}
}
// Driver code
let arr = [1, 2, 3, 4 , 5];
let n = arr.length;
let l = [1, 1, 2];
let r = [2, 3, 4];
let q = l.length;
wrapper(arr, n, l, r, q);
</script>
Producción
0 2 6
Complejidad temporal: O(n)
Espacio auxiliar: O(n)