Dada una array arr[] de tamaño N , la tarea es contar el número de subarreglos de la array dada cuyo Bitwise XOR es par.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 4
Explicación: Los subarreglos que tienen incluso Bitwise XOR son { {2}, {4}, {1, 2, 3}, {1, 2, 3 , 4}}.Entrada: arr[] = {2, 4, 6}
Salida: 6
Explicación: Los subarreglos que tienen incluso Bitwise XOR son { {2}, {4}, {6}, {2, 4}, {4, 6}, {2, 4, 6}}.
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos posibles y verificar para cada subarreglo , si Bitwise XOR de todos sus elementos son pares o no. Si se encuentra parejo, aumente el conteo. Finalmente, imprima el conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// subarrays having even Bitwise XOR
void evenXorSubarray(int arr[], int n)
{
// Store the required result
int ans = 0;
// Generate subarrays with
// arr[i] as the first element
for (int i = 0; i < n; i++) {
// Store XOR of current subarray
int XOR = 0;
// Generate subarrays with
// arr[j] as the last element
for (int j = i; j < n; j++) {
// Calculate Bitwise XOR
// of the current subarray
XOR = XOR ^ arr[j];
// If XOR is even,
// increase ans by 1
if ((XOR & 1) == 0)
ans++;
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Stores the size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
evenXorSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to count the number of
// subarrays having even Bitwise XOR
static void evenXorSubarray(int arr[], int n)
{
// Store the required result
int ans = 0;
// Generate subarrays with
// arr[i] as the first element
for (int i = 0; i < n; i++) {
// Store XOR of current subarray
int XOR = 0;
// Generate subarrays with
// arr[j] as the last element
for (int j = i; j < n; j++) {
// Calculate Bitwise XOR
// of the current subarray
XOR = XOR ^ arr[j];
// If XOR is even,
// increase ans by 1
if ((XOR & 1) == 0)
ans++;
}
}
// Print the result
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Stores the size of the array
int N = arr.length;
evenXorSubarray(arr, N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to count the number of # subarrays having even Bitwise XOR def evenXorSubarray(arr, n): # Store the required result ans = 0 # Generate subarrays with # arr[i] as the first element for i in range(n): # Store XOR of current subarray XOR = 0 # Generate subarrays with # arr[j] as the last element for j in range(i, n): # Calculate Bitwise XOR # of the current subarray XOR = XOR ^ arr[j] # If XOR is even, # increase ans by 1 if ((XOR & 1) == 0): ans += 1 # Print the result print (ans) # Driver Code if __name__ == '__main__': # Given array arr = [1, 2, 3, 4] # Stores the size of the array N = len(arr) # Function Call evenXorSubarray(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the number of
// subarrays having even Bitwise XOR
static void evenXorSubarray(int[] arr, int n)
{
// Store the required result
int ans = 0;
// Generate subarrays with
// arr[i] as the first element
for (int i = 0; i < n; i++) {
// Store XOR of current subarray
int XOR = 0;
// Generate subarrays with
// arr[j] as the last element
for (int j = i; j < n; j++) {
// Calculate Bitwise XOR
// of the current subarray
XOR = XOR ^ arr[j];
// If XOR is even,
// increase ans by 1
if ((XOR & 1) == 0)
ans++;
}
}
// Print the result
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
// Given array
int[] arr = { 1, 2, 3, 4 };
// Stores the size of the array
int N = arr.Length;
evenXorSubarray(arr, N);
}
}
// This code is contributed by souravghosh0416.
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// subarrays having even Bitwise XOR
function evenXorSubarray(arr, n)
{
// Store the required result
let ans = 0;
// Generate subarrays with
// arr[i] as the first element
for (let i = 0; i < n; i++) {
// Store XOR of current subarray
let XOR = 0;
// Generate subarrays with
// arr[j] as the last element
for (let j = i; j < n; j++) {
// Calculate Bitwise XOR
// of the current subarray
XOR = XOR ^ arr[j];
// If XOR is even,
// increase ans by 1
if ((XOR & 1) == 0)
ans++;
}
}
// Print the result
document.write(ans);
}
// Driver Code
// Given array
let arr = [ 1, 2, 3, 4 ];
// Stores the size of the array
let N = arr.length;
// Function Call
evenXorSubarray(arr, N);
</script>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
XOR bit a bit de todos los elementos en el rango de índices [i + 1, j] sea A.
XOR bit a bit de todos los elementos en el rango de índices [0, i] sea B.
XOR bit a bit de todos los elementos en el rango de índices [0 , j] sea C .
Al realizar B ^ C , los elementos comunes de los dos rangos se cancelan, lo que da como resultado XOR de todos los elementos del rango [i + 1, j] .
Por lo tanto, la idea es actualizar el número de subarreglos a partir del índice 0, con valores XOR pares e impares mientras se recorre el arreglo y se actualiza el conteo en consecuencia. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos ans y XOR, para almacenar el conteo requerido de subarreglos y almacenar los valores XOR de los subarreglos respectivamente.
- Inicialice una array, digamos freq[] de tamaño 2, donde freq[0] denota el número de subarreglos que tienen un valor XOR par, y freq[1] denota el número de subarreglos que tienen valores XOR impares, comenzando desde el índice 0.
- Recorra el arreglo , arr[] usando una variable, digamos i , y para cada elemento del arreglo:
- Actualice el valor de XOR a XOR ^ arr[i] .
- Si XOR es par , aumente el valor de ans en 1 + freq[0] .
- Incremente freq[0] en 1, porque cuando el subarreglo {arr[0], i] es XOR con otros subarreglos que tienen un valor xor par, entonces resultaría en un valor XOR par. Además, se suma 1 para considerar todo el subarreglo [0, i].
- De manera similar, si XOR es impar , incremente ans por freq[1] e incremente freq[1] por 1.
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays
// having even Bitwise XOR
void evenXorSubarray(int arr[], int n)
{
// Store the required result
int ans = 0;
// Stores count of subarrays
// with even and odd XOR values
int freq[] = { 0, 0 };
// Stores Bitwise XOR of
// current subarray
int XOR = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Update current Xor
XOR = XOR ^ arr[i];
// If XOR is even
if (XOR % 2 == 0) {
// Update ans
ans += freq[0] + 1;
// Increment count of
// subarrays with even XOR
freq[0]++;
}
else {
// Otherwise, increment count
// of subarrays with odd XOR
ans += freq[1];
freq[1]++;
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Stores the size of the array
int N = sizeof(arr) / sizeof(arr[0]);
evenXorSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to count subarrays
// having even Bitwise XOR
static void evenXorSubarray(int arr[], int n)
{
// Store the required result
int ans = 0;
// Stores count of subarrays
// with even and odd XOR values
int freq[] = { 0, 0 };
// Stores Bitwise XOR of
// current subarray
int XOR = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Update current Xor
XOR = XOR ^ arr[i];
// If XOR is even
if (XOR % 2 == 0) {
// Update ans
ans += freq[0] + 1;
// Increment count of
// subarrays with even XOR
freq[0]++;
}
else {
// Otherwise, increment count
// of subarrays with odd XOR
ans += freq[1];
freq[1]++;
}
}
// Print the result
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Stores the size of the array
int N = arr.length;
evenXorSubarray(arr, N);
}
}
Python3
# Python3 program for the above approach # Function to count subarrays # having even Bitwise XOR def evenXorSubarray(arr, n): # Store the required result ans = 0 # Stores count of subarrays # with even and odd XOR values freq = [0] * n # Stores Bitwise XOR of # current subarray XOR = 0 # Traverse the array for i in range(n): # Update current Xor XOR = XOR ^ arr[i] # If XOR is even if (XOR % 2 == 0): # Update ans ans += freq[0] + 1 # Increment count of # subarrays with even XOR freq[0] += 1 else: # Otherwise, increment count # of subarrays with odd XOR ans += freq[1] freq[1] += 1 # Print the result print(ans) # Driver Code # Given array arr = [ 1, 2, 3, 4 ] # Stores the size of the array N = len(arr) evenXorSubarray(arr, N) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count subarrays
// having even Bitwise XOR
static void evenXorSubarray(int[] arr, int n)
{
// Store the required result
int ans = 0;
// Stores count of subarrays
// with even and odd XOR values
int[] freq = { 0, 0 };
// Stores Bitwise XOR of
// current subarray
int XOR = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Update current Xor
XOR = XOR ^ arr[i];
// If XOR is even
if (XOR % 2 == 0) {
// Update ans
ans += freq[0] + 1;
// Increment count of
// subarrays with even XOR
freq[0]++;
}
else {
// Otherwise, increment count
// of subarrays with odd XOR
ans += freq[1];
freq[1]++;
}
}
// Print the result
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] arr = { 1, 2, 3, 4 };
// Stores the size of the array
int N = arr.Length;
evenXorSubarray(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
// Javascript program for the above approach
// Function to count subarrays
// having even Bitwise XOR
function evenXorSubarray(arr, n)
{
// Store the required result
let ans = 0;
// Stores count of subarrays
// with even and odd XOR values
let freq = [ 0, 0 ];
// Stores Bitwise XOR of
// current subarray
let XOR = 0;
// Traverse the array
for (let i = 0; i < n; i++) {
// Update current Xor
XOR = XOR ^ arr[i];
// If XOR is even
if (XOR % 2 == 0) {
// Update ans
ans += freq[0] + 1;
// Increment count of
// subarrays with even XOR
freq[0]++;
}
else {
// Otherwise, increment count
// of subarrays with odd XOR
ans += freq[1];
freq[1]++;
}
}
// Print the result
document.write(ans);
}
// Driver Code
// Given array
let arr = [ 1, 2, 3, 4 ];
// Stores the size of the array
let N = arr.length;
evenXorSubarray(arr, N);
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por singhprashant8759 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA