Dada una array arr[] de tamaño N , la tarea es contar todos los posibles subarreglos de longitud par que tengan un XOR bit a bit de elementos de subarreglo igual a 0 .
Ejemplos:
Entrada: arr[] = {2, 2, 3, 3, 6, 7, 8}
Salida: 3
Explicación:
Los subarreglos que tienen XOR de elementos igual a 0 son: {{2, 2}, {3, 3}, { 2, 2, 3, 3}}
Por lo tanto, la salida requerida es 3.Entrada: arr[] = {1, 2, 3, 3}
Salida: 1
Enfoque ingenuo: el enfoque más simple es recorrer el arreglo y generar todos los subarreglos posibles . Para cada subarreglo, compruebe si la longitud del subarreglo es par y si el XOR bit a bit de los elementos del subarreglo es 0 o no. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res para almacenar el recuento de subarreglos que satisfacen la condición dada.
- Atraviese el arreglo y genere todos los subarreglos posibles .
- Para cada subarreglo, verifique si la longitud del subarreglo es par y el XOR bit a bit de sus elementos es 0, luego incremente la resolución en 1.
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number
// of even-length subarrays
// having Bitwise XOR equal to 0
int cntSubarr(int arr[], int N)
{
// Stores the count of
// required subarrays
int res = 0;
// Stores prefix-XOR
// of arr[i, i+1, ...N-1]
int prefixXor = 0;
// Traverse the array
for (int i = 0; i < N - 1;
i++) {
prefixXor = arr[i];
for (int j = i + 1; j < N;
j++) {
// Calculate the prefix-XOR
// of current subarray
prefixXor ^= arr[j];
// Check if XOR of the
// current subarray is 0
// and length is even
if (prefixXor == 0
&& (j - i + 1) % 2 == 0) {
res++;
}
}
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 2, 2, 3, 3, 6, 7, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntSubarr(arr, N);
}
C
// C program to implement
// the above approach
#include <stdio.h>
// Function to count the number
// of even-length subarrays
// having Bitwise XOR equal to 0
int cntSubarr(int arr[], int N)
{
// Stores the count of
// required subarrays
int res = 0;
// Stores prefix-XOR
// of arr[i, i+1, ...N-1]
int prefixXor = 0;
// Traverse the array
for (int i = 0; i < N - 1;
i++) {
prefixXor = arr[i];
for (int j = i + 1; j < N;
j++) {
// Calculate the prefix-XOR
// of current subarray
prefixXor ^= arr[j];
// Check if XOR of the
// current subarray is 0
// and length is even
if (prefixXor == 0
&& (j - i + 1) % 2 == 0) {
res++;
}
}
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 2, 2, 3, 3, 6, 7, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", cntSubarr(arr, N));
}
// This code is contributed by phalashi.
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to count the number
// of even-length subarrays
// having Bitwise XOR equal to 0
static int cntSubarr(int arr[], int N)
{
// Stores the count of
// required subarrays
int res = 0;
// Stores prefix-XOR
// of arr[i, i+1, ...N-1]
int prefixXor = 0;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
prefixXor = arr[i];
for(int j = i + 1; j < N; j++)
{
// Calculate the prefix-XOR
// of current subarray
prefixXor ^= arr[j];
// Check if XOR of the
// current subarray is 0
// and length is even
if (prefixXor == 0 &&
(j - i + 1) % 2 == 0)
{
res++;
}
}
}
return res;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 2, 2, 3, 3, 6, 7, 8 };
int N = arr.length;
System.out.println(cntSubarr(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach # Function to count the number # of even-length subarrays # having Bitwise XOR equal to 0 def cntSubarr(arr, N): # Stores the count of # required subarrays res = 0 # Stores prefix-XOR # of arr[i, i+1, ...N-1] prefixXor = 0 # Traverse the array for i in range(N - 1): prefixXor = arr[i] for j in range(i + 1, N): # Calculate the prefix-XOR # of current subarray prefixXor ^= arr[j] # Check if XOR of the # current subarray is 0 # and length is even if (prefixXor == 0 and (j - i + 1) % 2 == 0): res += 1 return res # Driver Code if __name__ == '__main__': arr = [ 2, 2, 3, 3, 6, 7, 8 ] N = len(arr) print(cntSubarr(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to count the number
// of even-length subarrays
// having Bitwise XOR equal to 0
static int cntSubarr(int[] arr, int N)
{
// Stores the count of
// required subarrays
int res = 0;
// Stores prefix-XOR
// of arr[i, i+1, ...N-1]
int prefixXor = 0;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
prefixXor = arr[i];
for(int j = i + 1; j < N; j++)
{
// Calculate the prefix-XOR
// of current subarray
prefixXor ^= arr[j];
// Check if XOR of the
// current subarray is 0
// and length is even
if (prefixXor == 0 &&
(j - i + 1) % 2 == 0)
{
res++;
}
}
}
return res;
}
// Driver Code
public static void Main ()
{
int[] arr = { 2, 2, 3, 3, 6, 7, 8 };
int N = arr.Length;
Console.WriteLine(cntSubarr(arr, N));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count the number
// of even-length subarrays
// having Bitwise XOR equal to 0
function cntSubarr(arr, N)
{
// Stores the count of
// required subarrays
var res = 0;
// Stores prefix-XOR
// of arr[i, i+1, ...N-1]
var prefixXor = 0;
var i,j;
// Traverse the array
for (i = 0; i < N - 1;
i++) {
prefixXor = arr[i];
for (j = i + 1; j < N;
j++) {
// Calculate the prefix-XOR
// of current subarray
prefixXor ^= arr[j];
// Check if XOR of the
// current subarray is 0
// and length is even
if (prefixXor == 0
&& (j - i + 1) % 2 == 0) {
res++;
}
}
}
return res;
}
// Driver Code
var arr = [2, 2, 3, 3, 6, 7, 8];
var N = arr.length;
document.write(cntSubarr(arr, N));
</script>
Producción
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente : el problema se puede resolver utilizando Hashing . La idea es almacenar la frecuencia del Prefijo Xor en dos arrays separadas, digamos Odd[] y Even[] , para almacenar la frecuencia del Prefijo XOR de los índices pares e impares de la array dada. Finalmente, imprima el recuento de todos los pares posibles de las arrays Even[] y Odd[] que tengan un valor mayor o igual que 2 . Las siguientes son las observaciones:
Índice impar – Índice impar = Longitud
par Índice par – Índice par = Longitud parSi Even[X] ≥ 2: Bitwise XOR de todos los elementos entre dos índices pares del arreglo dado debe ser 0 y la longitud del subarreglo también es un número par (Indice par – Índice par).
Si Odd[X] ≥ 2: Bitwise XOR de todos los elementos entre dos índices impares del arreglo dado debe ser 0 y la longitud del subarreglo también es un número par (Índice impar – Índice impar).
Siga los pasos a continuación para resolver el problema:
- Inicialice dos arreglos, digamos Par[] e Impar[] para almacenar la frecuencia del Prefijo XOR en índices pares e impares del arreglo dado respectivamente.
- Inicialice una variable, digamos cntSub , para almacenar el recuento de subarreglos que satisfacen la condición dada.
- Recorra la array dada y calcule el Prefijo Xor de la array dada.
- Almacene la frecuencia del Prefijo XOR en índices pares e impares de la array dada en las arrays Par[] e Impar[] respectivamente.
- Finalmente, imprima el conteo de todos los pares posibles de pares [] e impares [] que tengan un valor mayor o igual a 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define M 1000000
// Function to get the count
// of even length subarrays
// having bitwise xor 0
int cntSubXor(int arr[], int N)
{
// Stores prefix-xor of
// the given array
int prefixXor = 0;
// Stores prefix-xor at
// even index of the array.
int Even[M];
// Stores prefix-xor at
// odd index of the array.
int Odd[M];
// Stores count of subarrays
// that satisfy the condition
int cntSub = 0;
// length from 0 index
// to odd index is even
Odd[0] = 1;
// Traverse the array.
for (int i = 0; i < N; i++) {
// Take prefix-xor
prefixXor ^= arr[i];
// If index is odd
if (i % 2 == 1) {
// Calculate pairs
cntSub += Odd[prefixXor];
// Increment prefix-xor
// at odd index
Odd[prefixXor]++;
}
else {
// Calculate pairs
cntSub += Even[prefixXor];
// Increment prefix-xor
// at odd index
Even[prefixXor]++;
}
}
return cntSub;
}
// Driver Code
int main()
{
int arr[] = { 2, 2, 3, 3, 6, 7, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntSubXor(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static final int M = 1000000;
// Function to get the count
// of even length subarrays
// having bitwise xor 0
static int cntSubXor(int arr[], int N)
{
// Stores prefix-xor of
// the given array
int prefixXor = 0;
// Stores prefix-xor at
// even index of the array.
int []Even = new int[M];
// Stores prefix-xor at
// odd index of the array.
int []Odd = new int[M];
// Stores count of subarrays
// that satisfy the condition
int cntSub = 0;
// length from 0 index
// to odd index is even
Odd[0] = 1;
// Traverse the array.
for(int i = 0; i < N; i++)
{
// Take prefix-xor
prefixXor ^= arr[i];
// If index is odd
if (i % 2 == 1)
{
// Calculate pairs
cntSub += Odd[prefixXor];
// Increment prefix-xor
// at odd index
Odd[prefixXor]++;
}
else
{
// Calculate pairs
cntSub += Even[prefixXor];
// Increment prefix-xor
// at odd index
Even[prefixXor]++;
}
}
return cntSub;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 2, 3, 3, 6, 7, 8 };
int N = arr.length;
System.out.print(cntSubXor(arr, N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach M = 1000000; # Function to get the count # of even length subarrays # having bitwise xor 0 def cntSubXor(arr, N): # Stores prefix-xor of # the given array prefixXor = 0; # Stores prefix-xor at # even index of the array. Even =[0] * M; # Stores prefix-xor at # odd index of the array. Odd = [0] * M; # Stores count of subarrays # that satisfy the condition cntSub = 0; # length from 0 index # to odd index is even Odd[0] = 1; # Traverse the array. for i in range(0, N): # Take prefix-xor prefixXor ^= arr[i]; # If index is odd if (i % 2 == 1): # Calculate pairs cntSub += Odd[prefixXor]; # Increment prefix-xor # at odd index Odd[prefixXor] += 1; else: # Calculate pairs cntSub += Even[prefixXor]; # Increment prefix-xor # at odd index Even[prefixXor] += 1; return cntSub; # Driver Code if __name__ == '__main__': arr = [2, 2, 3, 3, 6, 7, 8]; N = len(arr); print(cntSubXor(arr, N)); # This code is contributed by gauravrajput1
C#
// C# program to implement
// the above approach
using System;
class GFG{
static readonly int M = 1000000;
// Function to get the count
// of even length subarrays
// having bitwise xor 0
static int cntSubXor(int []arr, int N)
{
// Stores prefix-xor of
// the given array
int prefixXor = 0;
// Stores prefix-xor at
// even index of the array.
int []Even = new int[M];
// Stores prefix-xor at
// odd index of the array.
int []Odd = new int[M];
// Stores count of subarrays
// that satisfy the condition
int cntSub = 0;
// length from 0 index
// to odd index is even
Odd[0] = 1;
// Traverse the array.
for(int i = 0; i < N; i++)
{
// Take prefix-xor
prefixXor ^= arr[i];
// If index is odd
if (i % 2 == 1)
{
// Calculate pairs
cntSub += Odd[prefixXor];
// Increment prefix-xor
// at odd index
Odd[prefixXor]++;
}
else
{
// Calculate pairs
cntSub += Even[prefixXor];
// Increment prefix-xor
// at odd index
Even[prefixXor]++;
}
}
return cntSub;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 2, 3, 3, 6, 7, 8 };
int N = arr.Length;
Console.Write(cntSubXor(arr, N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
let M = 1000000;
// Function to get the count
// of even length subarrays
// having bitwise xor 0
function cntSubXor(arr, N)
{
// Stores prefix-xor of
// the given array
let prefixXor = 0;
// Stores prefix-xor at
// even index of the array.
let Even = Array.from({length: M}, (_, i) => 0);
// Stores prefix-xor at
// odd index of the array.
let Odd = Array.from({length: M}, (_, i) => 0);
// Stores count of subarrays
// that satisfy the condition
let cntSub = 0;
// length from 0 index
// to odd index is even
Odd[0] = 1;
// Traverse the array.
for(let i = 0; i < N; i++)
{
// Take prefix-xor
prefixXor = Math.floor(prefixXor ^ arr[i]);
// If index is odd
if (i % 2 == 1)
{
// Calculate pairs
cntSub += Odd[prefixXor];
// Increment prefix-xor
// at odd index
Odd[prefixXor]++;
}
else
{
// Calculate pairs
cntSub += Even[prefixXor];
// Increment prefix-xor
// at odd index
Even[prefixXor]++;
}
}
return cntSub;
}
// Driver Code
let arr = [ 2, 2, 3, 3, 6, 7, 8 ];
let N = arr.length;
document.write(cntSubXor(arr, N));
// This code is contributed by target_2
</script>
Producción
3
Complejidad de tiempo: O(N)
Espacio auxiliar: O(M), donde M es el XOR bit a bit máximo posible en todos los subarreglos.
Publicación traducida automáticamente
Artículo escrito por dbarnwal888 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA