Dado un arreglo de enteros, arr[] de tamaño N. El valor XOR de cualquier subarreglo de arr[] se define como el xor de todos los enteros en ese subarreglo. La tarea es encontrar el número de subarreglos con valor XOR una potencia de 2. (1, 2, 4, 8, 16, ….)
Ejemplos:
Input : arr[] = {2, 6, 7, 5, 8}
Output : 6
Subarrays : {2, 6}, {2}, {6, 7}, {6, 7, 5}, {7, 5}, {8}
Input : arr[] = {2, 4, 8, 16}
Output : 4
Enfoque :
- Mantenga un hashmap que almacene todos los valores XOR de prefijo y sus recuentos.
- En cualquier índice i, necesitamos encontrar el número de subarreglos que terminan en i y tienen un valor XOR potencia de 2. Necesitamos encontrar para toda la potencia de 2, el número de subarreglos posibles. Por ejemplo. : Supongamos que el valor XOR actual hasta que el índice i sea X, necesitamos encontrar el número de subarreglos que dan como resultado 16 (digamos S), por lo que necesitamos el conteo del prefijo XOR Y tal que (X^Y) = S o Y = S ^ X. Y se puede encontrar usando Hash Map.
- Realice el Paso 2, para todo el índice, agregue la salida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to count number of subarrays
// with Bitwise-XOR as power of 2
#include <bits/stdc++.h>
#define ll long long int
#define MAX 10
using namespace std;
// Function to find number of subarrays
int findSubarray(int array[], int n)
{
// Hash Map to store prefix XOR values
unordered_map<int, int> mp;
// When no element is selected
mp.insert({ 0, 1 });
int answer = 0;
int preXor = 0;
for (int i = 0; i < n; i++) {
int value = 1;
preXor ^= array[i];
// Check for all the powers of 2,
// till a MAX value
for (int j = 1; j <= MAX; j++) {
int Y = value ^ preXor;
if (mp.find(Y) != mp.end()) {
answer += mp[Y];
}
value *= 2;
}
// Insert Current prefixxor in Hash Map
if (mp.find(preXor) != mp.end()) {
mp[preXor]++;
}
else {
mp.insert({ preXor, 1 });
}
}
return answer;
}
// Driver Code
int main()
{
int array[] = { 2, 6, 7, 5, 8 };
int n = sizeof(array) / sizeof(array[0]);
cout << findSubarray(array, n) << endl;
return 0;
}
Java
// Java Program to count number of subarrays
// with Bitwise-XOR as power of 2
import java.util.*;
class GFG
{
static int MAX = 10;
// Function to find number of subarrays
static int findSubarray(int array[], int n)
{
// Hash Map to store prefix XOR values
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// When no element is selected
mp.put(0, 1);
int answer = 0;
int preXor = 0;
for (int i = 0; i < n; i++)
{
int value = 1;
preXor ^= array[i];
// Check for all the powers of 2,
// till a MAX value
for (int j = 1; j <= MAX; j++)
{
int Y = value ^ preXor;
if (mp.containsKey(Y))
{
answer += mp.get(Y);
}
value *= 2;
}
// Insert Current prefixxor in Hash Map
if (mp.containsKey(preXor))
{
mp.put(preXor,mp.get(preXor) + 1);
}
else
{
mp.put(preXor, 1);
}
}
return answer;
}
// Driver Code
public static void main (String[] args)
{
int array[] = { 2, 6, 7, 5, 8 };
int n = array.length;
System.out.println(findSubarray(array, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 Program to count number of subarrays # with Bitwise-XOR as power of 2 MAX = 10 # Function to find number of subarrays def findSubarray(array, n): # Hash Map to store prefix XOR values mp = dict() # When no element is selected mp[0] = 1 answer = 0 preXor = 0 for i in range(n): value = 1 preXor ^= array[i] # Check for all the powers of 2, # till a MAX value for j in range(1, MAX + 1): Y = value ^ preXor if ( Y in mp.keys()): answer += mp[Y] value *= 2 # Insert Current prefixxor in Hash Map if (preXor in mp.keys()): mp[preXor] += 1 else: mp[preXor] = 1 return answer # Driver Code array = [2, 6, 7, 5, 8] n = len(array) print(findSubarray(array, n)) # This code is contributed by Mohit Kumar
C#
// C# Program to count number of subarrays
// with Bitwise-XOR as power of 2
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 10;
// Function to find number of subarrays
static int findSubarray(int []array, int n)
{
// Hash Map to store prefix XOR values
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// When no element is selected
mp.Add(0, 1);
int answer = 0;
int preXor = 0;
for (int i = 0; i < n; i++)
{
int value = 1;
preXor ^= array[i];
// Check for all the powers of 2,
// till a MAX value
for (int j = 1; j <= MAX; j++)
{
int Y = value ^ preXor;
if (mp.ContainsKey(Y))
{
answer += mp[Y];
}
value *= 2;
}
// Insert Current prefixxor in Hash Map
if (mp.ContainsKey(preXor))
{
mp[preXor] = mp[preXor] + 1;
}
else
{
mp.Add(preXor, 1);
}
}
return answer;
}
// Driver Code
public static void Main (String[] args)
{
int []array = { 2, 6, 7, 5, 8 };
int n = array.Length;
Console.WriteLine(findSubarray(array, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to count number of subarrays
// with Bitwise-XOR as power of 2
var MAX = 10;
// Function to find number of subarrays
function findSubarray(array, n)
{
// Hash Map to store prefix XOR values
var mp = new Map();
// When no element is selected
mp.set(0,1);
var answer = 0;
var preXor = 0;
for (var i = 0; i < n; i++) {
var value = 1;
preXor ^= array[i];
// Check for all the powers of 2,
// till a MAX value
for (var j = 1; j <= MAX; j++) {
var Y = value ^ preXor;
if (mp.has(Y)) {
answer += mp.get(Y);
}
value *= 2;
}
// Insert Current prefixxor in Hash Map
if (mp.has(preXor)) {
mp.set(preXor, mp.get(preXor)+1);
}
else {
mp.set(preXor,1);
}
}
return answer;
}
// Driver Code
var array = [2, 6, 7, 5, 8 ];
var n = array.length;
document.write( findSubarray(array, n));
</script>
Producción:
6
Complejidad de tiempo: O(n * MAX)
Espacio Auxiliar: O(n)