Dado un arreglo de enteros, necesitamos obtener el XOR total de todos los XOR del subarreglo, donde el XOR del subarreglo puede obtenerse mediante el XORing de todos los elementos del mismo.
Ejemplos:
Input : arr[] = [3, 5, 2, 4, 6]
Output : 7
Total XOR of all subarray XORs is,
(3) ^ (5) ^ (2) ^ (4) ^ (6)
(3^5) ^ (5^2) ^ (2^4) ^ (4^6)
(3^5^2) ^ (5^2^4) ^ (2^4^6)
(3^5^2^4) ^ (5^2^4^6) ^
(3^5^2^4^6) = 7
Input : arr[] = {1, 2, 3, 4}
Output : 0
Total XOR of all subarray XORs is,
(1) ^ (2) ^ (3) ^ (4) ^
(1^2) ^ (2^3) ^ (3^4) ^
(1^2^3) ^ (2^3^4) ^
(1^2^3^4) = 0
Hemos discutido una solución O (n) en la publicación a continuación.
XOR de todos los XOR de subarreglo | Conjunto 1
Como se discutió en la publicación anterior, la frecuencia del elemento en el i-ésimo índice está dada por (i + 1) * (Ni), donde N es el tamaño de la array
Hay 4 casos posibles:
- Caso 1: i es impar, N es impar
- Sea i = 2k+1, N = 2m+1
freq[i] = ((2k+1)+1)*((2m+1)-(2k+1)) = 4(mk)(k+1) = incluso- Caso 2: i es impar, N es par
- Sea i = 2k+1, N = 2m
freq[i] = ((2k+1)+1)*((2m)-(2k+1)) = 2(k+1)(2m-2k-1) = incluso- Caso 3: i es par, N es impar
- Sea i = 2k, N = 2m+1
freq[i] = ((2k)+1)*((2m+1)-(2k)) = 2k(2m-2k+1)+(2m-2k)+ 1 = impar- Caso 4: i es par, N es par
- Sea i = 2k, N = 2m
freq[i] = ((2k)+1)*((2m)-(2k)) = 2(mk)(2k+1) = par
De esto, podemos concluir que si el número total de elementos en la array es par, entonces la frecuencia del elemento en cualquier posición es par. Entonces el total XOR será 0. Y si el total no. de elementos son impares, entonces la frecuencia de elementos en posiciones pares es impar y la frecuencia de elementos en posiciones impares es par. Entonces necesitamos encontrar solo el XOR de elementos en posiciones pares.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to get total xor of all subarray xors
#include <bits/stdc++.h>
using namespace std;
// Returns XOR of all subarray xors
int getTotalXorOfSubarrayXors(int arr[], int N)
{
// if even number of terms are there, all
// numbers will appear even number of times.
// So result is 0.
if (N % 2 == 0)
return 0;
// else initialize result by 0 as (a xor 0 = a)
int res = 0;
for (int i = 0; i<N; i+=2)
res ^= arr[i];
return res;
}
// Driver code to test above methods
int main()
{
int arr[] = {3, 5, 2, 4, 6};
int N = sizeof(arr) / sizeof(arr[0]);
cout << getTotalXorOfSubarrayXors(arr, N);
return 0;
}
Java
// Java program to get total
// xor of all subarray xors
import java.io.*;
class GFG
{
// Returns XOR of all
// subarray xors
static int getTotalXorOfSubarrayXors(int arr[],
int N)
{
// if even number of terms are
// there, all numbers will appear
// even number of times. So result is 0.
if (N % 2 == 0)
return 0;
// else initialize result
// by 0 as (a xor 0 = a)
int res = 0;
for (int i = 0; i < N; i += 2)
res ^= arr[i];
return res;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {3, 5, 2, 4, 6};
int N = arr.length;
System.out.println(
getTotalXorOfSubarrayXors(arr, N));
}
}
// This code is contributed by ajit
Python3
# Python 3 program to get total xor # of all subarray xors # Returns XOR of all subarray xors def getTotalXorOfSubarrayXors(arr, N): # if even number of terms are there, # all numbers will appear even number # of times. So result is 0. if (N % 2 == 0): return 0 # else initialize result by 0 # as (a xor 0 = a) res = 0 for i in range(0, N, 2): res ^= arr[i] return res # Driver code if __name__ == "__main__": arr = [3, 5, 2, 4, 6] N = len(arr) print(getTotalXorOfSubarrayXors(arr, N)) # This code is contributed by ita_c
C#
// C# program to get total
// xor of all subarray xors
using System;
class GFG
{
// Returns XOR of all
// subarray xors
static int getTotalXorOfSubarrayXors(int []arr,
int N)
{
// if even number of terms
// are there, all numbers
// will appear even number
// of times. So result is 0.
if (N % 2 == 0)
return 0;
// else initialize result
// by 0 as (a xor 0 = a)
int res = 0;
for (int i = 0; i < N; i += 2)
res ^= arr[i];
return res;
}
// Driver Code
static void Main()
{
int []arr = {3, 5, 2, 4, 6};
int N = arr.Length;
Console.Write(getTotalXorOfSubarrayXors(arr, N));
}
}
// This code is contributed by aj_36
PHP
<?php
// PHP program to get total
// xor of all subarray xors
// Returns XOR of all subarray xors
function getTotalXorOfSubarrayXors($arr, $N)
{
// if even number of terms
// are there, all numbers
// will appear even number
// of times. So result is 0.
if ($N % 2 == 0)
return 0;
// else initialize result
// by 0 as (a xor 0 = a)
$res = 0;
for ($i = 0; $i < $N; $i += 2)
$res ^= $arr[$i];
return $res;
}
// Driver Code
$arr = array(3, 5, 2, 4, 6);
$N = count($arr);
echo getTotalXorOfSubarrayXors($arr, $N);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to get total
// xor of all subarray xors
// Returns XOR of all
// subarray xors
function getTotalXorOfSubarrayXors(arr,N)
{
// if even number of terms are
// there, all numbers will appear
// even number of times. So result is 0.
if (N % 2 == 0)
return 0;
// else initialize result
// by 0 as (a xor 0 = a)
let res = 0;
for (let i = 0; i < N; i += 2)
{
res ^= arr[i];
}
return res;
}
// Driver Code
let arr=[3, 5, 2, 4, 6];
let N = arr.length;
document.write(getTotalXorOfSubarrayXors(arr, N));
// This code is contributed by avanitrachhadiya2155
</script>
7
Complejidad de tiempo: O(n), donde n es la longitud de la array dada
Espacio auxiliar: O(1)
Este artículo es una contribución de Rishabh Raj Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA