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}
Output : 2
Input : arr[] = {1, 2, 3, 4}
Output : 0
Una solución simple es generar todos los subarreglos y calcular XOR de todos ellos. A continuación se muestra la implementación de la idea anterior:
Implementación:
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)
{
// initialize result by 0 as (a xor 0 = a)
int res = 0;
// select the starting element
for (int i=0; i<N; i++)
// select the eNding element
for (int j=i; j<N; j++)
// Do XOR of elements in current subarray
for (int k=i; k<=j; k++)
res = res ^ arr[k];
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
public class GFG {
// Returns XOR of all subarray xors
static int getTotalXorOfSubarrayXors(
int arr[], int N)
{
// initialize result by
// 0 as (a xor 0 = a)
int res = 0;
// select the starting element
for (int i = 0; i < N; i++)
// select the eNding element
for (int j = i; j < N; j++)
// Do XOR of elements
// in current subarray
for (int k = i; k <= j; k++)
res = res ^ arr[k];
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 Sam007.
Python 3
# python program to get total xor # of all subarray xors # Returns XOR of all subarray xors def getTotalXorOfSubarrayXors(arr, N): # initialize result by 0 as # (a xor 0 = a) res = 0 # select the starting element for i in range(0, N): # select the eNding element for j in range(i, N): # Do XOR of elements in # current subarray for k in range(i, j + 1): res = res ^ arr[k] return res # Driver code to test above methods arr = [3, 5, 2, 4, 6] N = len(arr) print(getTotalXorOfSubarrayXors(arr, N)) # This code is contributed by Sam007.
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)
{
// initialize result by
// 0 as (a xor 0 = a)
int res = 0;
// select the starting element
for (int i = 0; i < N; i++)
// select the eNding element
for (int j = i; j < N; j++)
// Do XOR of elements
// in current subarray
for (int k = i; k <= j; k++)
res = res ^ arr[k];
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 Sam007
PHP
<?php
// PHP program to get total
// xor of all subarray xors
// Returns XOR of all subarray xors
function getTotalXorOfSubarrayXors($arr, $N)
{
// initialize result by
// 0 as (a xor 0 = a)
$res = 0;
// select the starting element
for($i = 0; $i < $N; $i++)
// select the eNding element
for($j = $i; $j < $N; $j++)
// Do XOR of elements in
// current subarray
for($k = $i; $k <= $j; $k++)
$res = $res ^ $arr[$k];
return $res;
}
// Driver code
$arr = array(3, 5, 2, 4, 6);
$N = sizeof($arr);
echo getTotalXorOfSubarrayXors($arr, $N);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program for the above approach
// Returns XOR of all subarray xors
function getTotalXorOfSubarrayXors(
arr, N)
{
// initialize result by
// 0 as (a xor 0 = a)
let res = 0;
// select the starting element
for (let i = 0; i < N; i++)
// select the eNding element
for (let j = i; j < N; j++)
// Do XOR of elements
// in current subarray
for (let k = i; k <= j; k++)
res = res ^ arr[k];
return res;
}
// Driver Code
// Both a[] and b[] must be of same size.
let arr = [3, 5, 2, 4, 6];
let N = arr.length;
document.write(getTotalXorOfSubarrayXors(arr, N));
// This code is contributed by code_hunt.
</script>
Producción
7
Complejidad temporal: O(N 3 )
Una solución eficiente se basa en la idea de enumerar todos los subarreglos, podemos contar la frecuencia de cada elemento que ocurrió totalmente en todos los subarreglos, si la frecuencia de un elemento es impar, se incluirá en el resultado final, de lo contrario no lo será.
As in above example, 3 occurred 5 times, 5 occurred 8 times, 2 occurred 9 times, 4 occurred 8 times, 6 occurred 5 times So our final result will be xor of all elements which occurred odd number of times i.e. 3^2^6 = 7 From above occurrence pattern we can observe that number at i-th index will have (i + 1) * (N - i) frequency.
Entonces, podemos iterar sobre todos los elementos una vez y calcular sus frecuencias y, si es impar, podemos incluirlo en nuestro resultado final mediante XOR con el resultado.
La complejidad temporal total de la solución será O(N)
Implementación:
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)
{
// initialize result by 0
// as (a XOR 0 = a)
int res = 0;
// loop over all elements once
for (int i = 0; i < N; i++)
{
// get the frequency of
// current element
int freq = (i + 1) * (N - i);
// Uncomment below line to print
// the frequency of arr[i]
// cout << arr[i] << " " << freq << endl;
// if frequency is odd, then
// include it in the result
if (freq % 2 == 1)
res = res ^ arr[i];
}
// return the result
return res;
}
// Driver Code
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.*;
public class GFG {
// Returns XOR of all subarray
// xors
static int getTotalXorOfSubarrayXors(
int arr[], int N)
{
// initialize result by 0
// as (a XOR 0 = a)
int res = 0;
// loop over all elements once
for (int i = 0; i < N; i++)
{
// get the frequency of
// current element
int freq = (i + 1) * (N - i);
// Uncomment below line to print
// the frequency of arr[i]
// if frequency is odd, then
// include it in the result
if (freq % 2 == 1)
res = res ^ arr[i];
}
// return the result
return res;
}
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 Sam007.
Python 3
# Python3 program to get total # xor of all subarray xors # Returns XOR of all # subarray xors def getTotalXorOfSubarrayXors(arr, N): # initialize result by 0 # as (a XOR 0 = a) res = 0 # loop over all elements once for i in range(0, N): # get the frequency of # current element freq = (i + 1) * (N - i) # Uncomment below line to print # the frequency of arr[i] # if frequency is odd, then # include it in the result if (freq % 2 == 1): res = res ^ arr[i] # return the result return res # Driver Code arr = [3, 5, 2, 4, 6] N = len(arr) print(getTotalXorOfSubarrayXors(arr, N)) # This code is contributed # by Smitha
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)
{
// initialize result by 0
// as (a XOR 0 = a)
int res = 0;
// loop over all elements once
for (int i = 0; i < N; i++)
{
// get the frequency of
// current element
int freq = (i + 1) * (N - i);
// Uncomment below line to print
// the frequency of arr[i]
// if frequency is odd, then
// include it in the result
if (freq % 2 == 1)
res = res ^ arr[i];
}
// return the result
return res;
}
// Driver Code
public static void Main()
{
int []arr = {3, 5, 2, 4, 6};
int N = arr.Length;
Console.Write(getTotalXorOfSubarrayXors(arr, N));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to get total
// xor of all subarray xors
// Returns XOR of all subarray xors
function getTotalXorOfSubarrayXors($arr,
$N)
{
// initialize result by 0
// as (a XOR 0 = a)
$res = 0;
// loop over all elements once
for ($i = 0; $i < $N; $i++)
{
// get the frequency of
// current element
$freq = ($i + 1) * ($N - $i);
// if frequency is odd, then
// include it in the result
if ($freq % 2 == 1)
$res = $res ^ $arr[$i];
}
// return the result
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)
{
// initialize result by 0
// as (a XOR 0 = a)
let res = 0;
// loop over all elements once
for (let i = 0; i < N; i++)
{
// get the frequency of
// current element
let freq = (i + 1) * (N - i);
// Uncomment below line to print
// the frequency of arr[i]
// cout << arr[i] << " " << freq << endl;
// if frequency is odd, then
// include it in the result
if (freq % 2 == 1)
res = res ^ arr[i];
}
// return the result
return res;
}
// Driver Code
let arr = [3, 5, 2, 4, 6];
let N = arr.length;
document.write(getTotalXorOfSubarrayXors(arr, N));
</script>
Producción
7
Complejidad de tiempo : O(N)
Este artículo es una contribución de Utkarsh Trivedi . 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