Dado un arreglo de N números, la tarea es encontrar el número de sub-arreglos (el tamaño del subarreglo debe ser un número par) del arreglo dado tal que después de dividir el subarreglo en dos mitades iguales, bit a bit XOR de la mitad del subarreglo será igual a bit a bit XOR de la otra mitad.
Ejemplos:
Input : N = 6, arr[] = {3, 2, 2, 3, 7, 6}
Output : 3
Valid sub-arrays are {3, 2, 2, 3}, {2, 2},
and {2, 3, 7, 6}
Input : N = 5, arr[] = {1, 2, 3, 4, 5}
Output : 1
Input : N = 3, arr[] = {42, 4, 2}
Output : 0
Enfoque: si una array se divide en dos mitades iguales y el XOR de una mitad es igual a la otra, significa que el XOR de toda la array debe ser 0, porque A^A = 0. Ahora, para resolver el problema anterior, encuentre el prefijo XOR de todos los elementos de la array dada a partir de la izquierda.
Supongamos que un subarreglo comienza en l y termina en r , entonces (r-l+1) debería ser par . Además, para encontrar XOR de un rango dado (l, r) reste el prefijo XOR en (l – 1) con el prefijo XOR en r.
Dado que (r – l + 1) es par, por lo tanto, si r es par, entonces l debería ser impar y viceversa. Ahora, divide tus prefijos en dos grupos, uno debe ser el grupo de prefijos de índices impares y el otro debe ser de índices pares. Ahora, comience a recorrer la array de prefijos de izquierda a derecha y vea cuántas veces este prefijo A en particular ya se ha producido en su grupo respectivo, es decir, los prefijos en los índices pares deben verificarse en el grupo de prefijos pares y los prefijos en los índices impares en el grupo de prefijos impares ( porque si r es par entonces ( l -1) también es par, se aplica una lógica similar si r es impar).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of subarrays such that
// XOR of one half is equal to the other
#include <bits/stdc++.h>
using namespace std;
// Function to find number of subarrays such that
// XOR of one half is equal to the other
int findSubarrCnt(int arr[], int n)
{
// Variables to store answer and current XOR's
int ans = 0, XOR = 0;
// Array to store prefix XOR's
int prefix[n];
for (int i = 0; i < n; ++i) {
// Calculate XOR until this index
XOR = XOR ^ arr[i];
// Store the XOR in prefix array
prefix[i] = XOR;
}
// Create groups for odd indexes and even indexes
unordered_map<int, int> oddGroup, evenGroup;
// Initialize occurrence of 0 in oddGroup as 1
// because it will be used in case our
// subarray has l = 0
oddGroup[0] = 1;
for (int i = 0; i < n; ++i) {
if (i & 1) {
// Check the frequency of current prefix
// XOR in oddGroup and add it to the
// answer
ans += oddGroup[prefix[i]];
// Update the frequency
++oddGroup[prefix[i]];
}
else {
// Check the frequency of current prefix
// XOR in evenGroup and add it to the
// answer
ans += evenGroup[prefix[i]];
// Update the frequency
++evenGroup[prefix[i]];
}
}
return ans;
}
// Driver Code
int main()
{
int N = 6;
int arr[] = { 3, 2, 2, 3, 7, 6 };
cout << findSubarrCnt(arr, N);
return 0;
}
Java
// JAVA program to find number of subarrays such that
// XOR of one half is equal to the other
import java.util.*;
class GFG
{
// Function to find number of subarrays such that
// XOR of one half is equal to the other
static int findSubarrCnt(int arr[], int n)
{
// Variables to store answer and current XOR's
int ans = 0, XOR = 0;
// Array to store prefix XOR's
int prefix[] = new int[n];
for (int i = 0; i < n; ++i)
{
// Calculate XOR until this index
XOR = XOR ^ arr[i];
// Store the XOR in prefix array
prefix[i] = XOR;
}
// Create groups for odd indexes and even indexes
HashMap<Integer, Integer> evenGroup = new HashMap<>();
HashMap<Integer, Integer> oddGroup = new HashMap<>();
// Initialize occurrence of 0 in oddGroup as 1
// because it will be used in case our
// subarray has l = 0
oddGroup.put(0, 1);
for (int i = 0; i < n; ++i)
{
if (i % 2== 1)
{
// Check the frequency of current prefix
// XOR in oddGroup and add it to the
// answer
if(oddGroup.containsKey(prefix[i]))
{
ans += oddGroup.get(prefix[i]);
// Update the frequency
oddGroup.put(prefix[i],oddGroup.get(prefix[i] + 1));
}
else
{
oddGroup.put(prefix[i], 1);
}
}
else
{
// Check the frequency of current prefix
// XOR in evenGroup and add it to the
// answer
if(evenGroup.containsKey(prefix[i]))
{
ans += evenGroup.get(prefix[i]);
// Update the frequency
evenGroup.put(prefix[i],evenGroup.get(prefix[i] + 1));
}
else
{
evenGroup.put(prefix[i], 1);
}
}
}
return ans;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 3, 2, 2, 3, 7, 6 };
int N = arr.length;
System.out.println(findSubarrCnt(arr, N));
}
}
// This code is contributed by ihritik
Python3
# Python3 program to find number of subarrays # such that XOR of one half is equal to the other # Function to find number of subarrays # such that XOR of one half is equal # to the other def findSubarrCnt(arr, n) : # Variables to store answer # and current XOR's ans = 0; XOR = 0; # Array to store prefix XOR's prefix = [0] * n; for i in range(n) : # Calculate XOR until this index XOR = XOR ^ arr[i]; # Store the XOR in prefix array prefix[i] = XOR; # Create groups for odd indexes and # even indexes oddGroup = dict.fromkeys(prefix, 0) evenGroup = dict.fromkeys(prefix, 0) # Initialize occurrence of 0 in oddGroup # as 1 because it will be used in case # our subarray has l = 0 oddGroup[0] = 1; for i in range(n) : if (i & 1) : # Check the frequency of current # prefix XOR in oddGroup and add # it to the answer ans += oddGroup[prefix[i]]; # Update the frequency oddGroup[prefix[i]] += 1; else : # Check the frequency of current # prefix XOR in evenGroup and add # it to the answer ans += evenGroup[prefix[i]]; # Update the frequency evenGroup[prefix[i]] += 1; return ans; # Driver Code if __name__ == "__main__" : N = 6; arr = [ 3, 2, 2, 3, 7, 6 ]; print(findSubarrCnt(arr, N)); # This code is contributed by Ryuga
C#
// C# program to find number of subarrays such that
// XOR of one half is equal to the other
using System;
using System.Collections.Generic;
class GFG
{
// Function to find number of subarrays such that
// XOR of one half is equal to the other
static int findSubarrCnt(int [] arr, int n)
{
// Variables to store answer and current XOR's
int ans = 0, XOR = 0;
// Array to store prefix XOR's
int [] prefix = new int[n];
for (int i = 0; i < n; ++i)
{
// Calculate XOR until this index
XOR = XOR ^ arr[i];
// Store the XOR in prefix array
prefix[i] = XOR;
}
// Create groups for odd indexes and even indexes
Dictionary<int, int> evenGroup = new Dictionary<int, int>();
Dictionary<int, int> oddGroup = new Dictionary<int, int>();
// Initialize occurrence of 0 in oddGroup as 1
// because it will be used in case our
// subarray has l = 0
oddGroup[0] = 1;
for (int i = 0; i < n; ++i)
{
if (i % 2== 1)
{
// Check the frequency of current prefix
// XOR in oddGroup and add it to the
// answer
if(oddGroup.ContainsKey(prefix[i]))
{
ans += oddGroup[prefix[i]];
// Update the frequency
oddGroup[prefix[i]]++;
}
else
{
oddGroup[prefix[i]] = 1;
}
}
else
{
// Check the frequency of current prefix
// XOR in evenGroup and add it to the
// answer
if(evenGroup.ContainsKey(prefix[i]))
{
ans += evenGroup[prefix[i]];
// Update the frequency
evenGroup[prefix[i]]++;
}
else
{
evenGroup[prefix[i]] = 1;
}
}
}
return ans;
}
// Driver Code
public static void Main ()
{
int [] arr = { 3, 2, 2, 3, 7, 6 };
int N = arr.Length;
Console.WriteLine(findSubarrCnt(arr, N));
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript program to find number of subarrays such that
// XOR of one half is equal to the other
// Function to find number of subarrays such that
// XOR of one half is equal to the other
function findSubarrCnt(arr, n)
{
// Variables to store answer and current XOR's
let ans = 0, XOR = 0;
// Array to store prefix XOR's
let prefix = Array.from({length: n}, (_, i) => 0);
for (let i = 0; i < n; ++i)
{
// Calculate XOR until this index
XOR = XOR ^ arr[i];
// Store the XOR in prefix array
prefix[i] = XOR;
}
// Create groups for odd indexes and even indexes
let evenGroup = new Map();
let oddGroup = new Map();
// Initialize occurrence of 0 in oddGroup as 1
// because it will be used in case our
// subarray has l = 0
oddGroup.set(0, 1);
for (let i = 0; i < n; ++i)
{
if (i % 2== 1)
{
// Check the frequency of current prefix
// XOR in oddGroup and add it to the
// answer
if(oddGroup.has(prefix[i]))
{
ans += oddGroup.get(prefix[i]);
// Update the frequency
oddGroup.set(prefix[i],oddGroup.get(prefix[i] + 1));
}
else
{
oddGroup.set(prefix[i], 1);
}
}
else
{
// Check the frequency of current prefix
// XOR in evenGroup and add it to the
// answer
if(evenGroup.has(prefix[i]))
{
ans += evenGroup.get(prefix[i]);
// Update the frequency
evenGroup.set(prefix[i],evenGroup.get(prefix[i] + 1));
}
else
{
evenGroup.set(prefix[i], 1);
}
}
}
return ans;
}
// Driver code
let arr = [ 3, 2, 2, 3, 7, 6 ];
let N = arr.length;
document.write(findSubarrCnt(arr, N));
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por NaimishSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA