Dado un arreglo de enteros arr[] y un número m, cuente el número de subarreglos que tienen XOR de sus elementos como m.
Ejemplos:
Input : arr[] = {4, 2, 2, 6, 4}, m = 6
Output : 4
Explanation : The subarrays having XOR of
their elements as 6 are {4, 2},
{4, 2, 2, 6, 4}, {2, 2, 6},
and {6}
Input : arr[] = {5, 6, 7, 8, 9}, m = 5
Output : 2
Explanation : The subarrays having XOR of
their elements as 5 are {5}
and {5, 6, 7, 8, 9}
Una solución simple es usar dos bucles para recorrer todos los subarreglos posibles de arr[] y contar el número de subarreglos que tienen XOR de sus elementos como m.
Implementación:
C++
// A simple C++ Program to count all subarrays having
// XOR of elements as given value m
#include <bits/stdc++.h>
using namespace std;
// Simple function that returns count of subarrays
// of arr with XOR value equals to m
long long subarrayXor(int arr[], int n, int m)
{
long long ans = 0; // Initialize ans
// Pick starting point i of subarrays
for (int i = 0; i < n; i++) {
int xorSum = 0; // Store XOR of current subarray
// Pick ending point j of subarray for each i
for (int j = i; j < n; j++) {
// calculate xorSum
xorSum = xorSum ^ arr[j];
// If xorSum is equal to given value,
// increase ans by 1.
if (xorSum == m)
ans++;
}
}
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 4, 2, 2, 6, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 6;
cout << "Number of subarrays having given XOR is "
<< subarrayXor(arr, n, m);
return 0;
}
Java
// A simple Java Program to count all
// subarrays having XOR of elements
// as given value m
public class GFG {
// Simple function that returns
// count of subarrays of arr with
// XOR value equals to m
static long subarrayXor(int arr[],
int n, int m)
{
// Initialize ans
long ans = 0;
// Pick starting point i of
// subarrays
for (int i = 0; i < n; i++)
{
// Store XOR of current
// subarray
int xorSum = 0;
// Pick ending point j of
// subarray for each i
for (int j = i; j < n; j++)
{
// calculate xorSum
xorSum = xorSum ^ arr[j];
// If xorSum is equal to
// given value, increase
// ans by 1.
if (xorSum == m)
ans++;
}
}
return ans;
}
// Driver code
public static void main(String args[])
{
int[] arr = { 4, 2, 2, 6, 4 };
int n = arr.length;
int m = 6;
System.out.println("Number of subarrays"
+ " having given XOR is "
+ subarrayXor(arr, n, m));
}
}
// This code is contributed by Sam007.
Python3
# A simple Python3 Program to count all subarrays having
# XOR of elements as given value m
# Simple function that returns count of subarrays
# of arr with XOR value equals to m
def subarrayXor(arr, n, m):
ans = 0 # Initialize ans
# Pick starting point i of subarrays
for i in range(0,n):
xorSum = 0 # Store XOR of current subarray
# Pick ending point j of subarray for each i
for j in range(i,n):
# calculate xorSum
xorSum = xorSum ^ arr[j]
# If xorSum is equal to given value,
# increase ans by 1.
if (xorSum == m):
ans+=1
return ans
# Driver program to test above function
def main():
arr = [ 4, 2, 2, 6, 4 ]
n = len(arr)
m = 6
print("Number of subarrays having given XOR is "
, subarrayXor(arr, n, m))
if __name__ == '__main__':
main()
#this code contributed by 29AjayKumar
C#
// A simple C# Program to count all
// subarrays having XOR of elements
// as given value m
using System;
class GFG {
// Simple function that returns
// count of subarrays of arr
// with XOR value equals to m
static long subarrayXor(int[] arr,
int n, int m)
{
// Initialize ans
long ans = 0;
// Pick starting point i of
// subarrays
for (int i = 0; i < n; i++)
{
// Store XOR of current
// subarray
int xorSum = 0;
// Pick ending point j of
// subarray for each i
for (int j = i; j < n; j++)
{
// calculate xorSum
xorSum = xorSum ^ arr[j];
// If xorSum is equal to
// given value, increase
// ans by 1.
if (xorSum == m)
ans++;
}
}
return ans;
}
// Driver Program
public static void Main()
{
int[] arr = { 4, 2, 2, 6, 4 };
int n = arr.Length;
int m = 6;
Console.Write("Number of subarrays"
+ " having given XOR is "
+ subarrayXor(arr, n, m));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A simple PHP Program to
// count all subarrays having
// XOR of elements as given value m
// Simple function that returns
// count of subarrays of arr
// with XOR value equals to m
function subarrayXor($arr, $n,$m)
{
// Initialize ans
$ans = 0;
// Pick starting point
// i of subarrays
for ($i = 0; $i < $n; $i++)
{
// Store XOR of
// current subarray
$xorSum = 0;
// Pick ending point j of
// subarray for each i
for ($j = $i; $j < $n; $j++)
{
// calculate xorSum
$xorSum = $xorSum ^ $arr[$j];
// If xorSum is equal
// to given value,
// increase ans by 1.
if ($xorSum == $m)
$ans++;
}
}
return $ans;
}
// Driver Code
$arr = array(4, 2, 2, 6, 4);
$n = count($arr);
$m = 6;
echo "Number of subarrays having given XOR is "
, subarrayXor($arr, $n, $m);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A simple Javascript Program to
// count all subarrays having
// XOR of elements as given value m
// Simple function that
// returns count of subarrays
// of arr with XOR value equals to m
function subarrayXor(arr, n, m)
{
let ans = 0; // Initialize ans
// Pick starting point i of subarrays
for (let i = 0; i < n; i++)
{
// Store XOR of current subarray
let xorSum = 0;
// Pick ending point j of
// subarray for each i
for (let j = i; j < n; j++) {
// calculate xorSum
xorSum = xorSum ^ arr[j];
// If xorSum is equal to given value,
// increase ans by 1.
if (xorSum == m)
ans++;
}
}
return ans;
}
// Driver program to test above function
let arr = [ 4, 2, 2, 6, 4 ];
let n = arr.length;
let m = 6;
document.write(
"Number of subarrays having given XOR is "
+ subarrayXor(arr, n, m)
);
</script>
Producción
Number of subarrays having given XOR is 4
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
Una solución eficiente resuelve el problema anterior en tiempo O(n). Llamemos al XOR de todos los elementos en el rango [i+1, j] como A, en el rango [0, i] como B, y en el rango [0, j] como C. Si hacemos XOR de B con C, los elementos superpuestos en [0, i] de B y C se ponen a cero, y obtenemos XOR de todos los elementos en el rango [i+1, j], es decir, A. Dado que A = B XOR C, tenemos B = A XOR C. Ahora, si conocemos el valor de C y tomamos el valor de A como m, obtenemos la cuenta de A como la cuenta de todos los B que satisfacen esta relación. Esencialmente, obtenemos el recuento de todos los subarreglos que tienen XOR-sum m para cada C. A medida que tomamos la suma de este recuento total C, obtenemos nuestra respuesta.
1) Initialize ans as 0.
2) Compute xorArr, the prefix xor-sum array.
3) Create a map mp in which we store count of
all prefixes with XOR as a particular value.
4) Traverse xorArr and for each element in xorArr
(A) If m^xorArr[i] XOR exists in map, then
there is another previous prefix with
same XOR, i.e., there is a subarray ending
at i with XOR equal to m. We add count of
all such subarrays to result.
(B) If xorArr[i] is equal to m, increment ans by 1.
(C) Increment count of elements having XOR-sum
xorArr[i] in map by 1.
5) Return ans.
Implementación:
C++
// C++ Program to count all subarrays having
// XOR of elements as given value m with
// O(n) time complexity.
#include <bits/stdc++.h>
using namespace std;
// Returns count of subarrays of arr with XOR
// value equals to m
long long subarrayXor(int arr[], int n, int m)
{
long long ans = 0; // Initialize answer to be returned
// Create a prefix xor-sum array such that
// xorArr[i] has value equal to XOR
// of all elements in arr[0 ..... i]
int* xorArr = new int[n];
// Create map that stores number of prefix array
// elements corresponding to a XOR value
unordered_map<int, int> mp;
// Initialize first element of prefix array
xorArr[0] = arr[0];
// Computing the prefix array.
for (int i = 1; i < n; i++)
xorArr[i] = xorArr[i - 1] ^ arr[i];
// Calculate the answer
for (int i = 0; i < n; i++) {
// Find XOR of current prefix with m.
int tmp = m ^ xorArr[i];
// If above XOR exists in map, then there
// is another previous prefix with same
// XOR, i.e., there is a subarray ending
// at i with XOR equal to m.
ans = ans + ((long long)mp[tmp]);
// If this subarray has XOR equal to m itself.
if (xorArr[i] == m)
ans++;
// Add the XOR of this subarray to the map
mp[xorArr[i]]++;
}
// Return total count of subarrays having XOR of
// elements as given value m
return ans;
}
// Driver program to test above function
int main()
{
int arr[] = { 4, 2, 2, 6, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 6;
cout << "Number of subarrays having given XOR is "
<< subarrayXor(arr, n, m);
return 0;
}
Java
// Java Program to count all subarrays having
// XOR of elements as given value m with
// O(n) time complexity.
import java.util.*;
class GFG {
// Returns count of subarrays of arr with XOR
// value equals to m
static long subarrayXor(int arr[], int n, int m)
{
long ans = 0; // Initialize answer to be returned
// Create a prefix xor-sum array such that
// xorArr[i] has value equal to XOR
// of all elements in arr[0 ..... i]
int[] xorArr = new int[n];
// Create map that stores number of prefix array
// elements corresponding to a XOR value
HashMap<Integer, Integer> mp
= new HashMap<Integer, Integer>();
// Initialize first element of prefix array
xorArr[0] = arr[0];
// Computing the prefix array.
for (int i = 1; i < n; i++)
xorArr[i] = xorArr[i - 1] ^ arr[i];
// Calculate the answer
for (int i = 0; i < n; i++) {
// Find XOR of current prefix with m.
int tmp = m ^ xorArr[i];
// If above XOR exists in map, then there
// is another previous prefix with same
// XOR, i.e., there is a subarray ending
// at i with XOR equal to m.
ans = ans
+ (mp.containsKey(tmp) == false
? 0
: ((long)mp.get(tmp)));
// If this subarray has XOR equal to m itself.
if (xorArr[i] == m)
ans++;
// Add the XOR of this subarray to the map
if (mp.containsKey(xorArr[i]))
mp.put(xorArr[i], mp.get(xorArr[i]) + 1);
else
mp.put(xorArr[i], 1);
}
// Return total count of subarrays having XOR of
// elements as given value m
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 2, 2, 6, 4 };
int n = arr.length;
int m = 6;
System.out.print(
"Number of subarrays having given XOR is "
+ subarrayXor(arr, n, m));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 Program to count all subarrays
# having XOR of elements as given value m
# with O(n) time complexity.
# Returns count of subarrays of arr
# with XOR value equals to m
def subarrayXor(arr, n, m):
ans = 0 # Initialize answer to be returned
# Create a prefix xor-sum array such that
# xorArr[i] has value equal to XOR
# of all elements in arr[0 ..... i]
xorArr =[0 for _ in range(n)]
# Create map that stores number of prefix array
# elements corresponding to a XOR value
mp = dict()
# Initialize first element
# of prefix array
xorArr[0] = arr[0]
# Computing the prefix array.
for i in range(1, n):
xorArr[i] = xorArr[i - 1] ^ arr[i]
# Calculate the answer
for i in range(n):
# Find XOR of current prefix with m.
tmp = m ^ xorArr[i]
# If above XOR exists in map, then there
# is another previous prefix with same
# XOR, i.e., there is a subarray ending
# at i with XOR equal to m.
if tmp in mp.keys():
ans = ans + (mp[tmp])
# If this subarray has XOR
# equal to m itself.
if (xorArr[i] == m):
ans += 1
# Add the XOR of this subarray to the map
mp[xorArr[i]] = mp.get(xorArr[i], 0) + 1
# Return total count of subarrays having
# XOR of elements as given value m
return ans
# Driver Code
arr = [4, 2, 2, 6, 4]
n = len(arr)
m = 6
print("Number of subarrays having given XOR is",
subarrayXor(arr, n, m))
# This code is contributed by mohit kumar
C#
// C# Program to count all subarrays having
// XOR of elements as given value m with
// O(n) time complexity.
using System;
using System.Collections.Generic;
class GFG {
// Returns count of subarrays of arr with XOR
// value equals to m
static long subarrayXor(int[] arr, int n, int m)
{
long ans = 0; // Initialize answer to be returned
// Create a prefix xor-sum array such that
// xorArr[i] has value equal to XOR
// of all elements in arr[0 ..... i]
int[] xorArr = new int[n];
// Create map that stores number of prefix array
// elements corresponding to a XOR value
Dictionary<int, int> mp
= new Dictionary<int, int>();
// Initialize first element of prefix array
xorArr[0] = arr[0];
// Computing the prefix array.
for (int i = 1; i < n; i++)
xorArr[i] = xorArr[i - 1] ^ arr[i];
// Calculate the answer
for (int i = 0; i < n; i++) {
// Find XOR of current prefix with m.
int tmp = m ^ xorArr[i];
// If above XOR exists in map, then there
// is another previous prefix with same
// XOR, i.e., there is a subarray ending
// at i with XOR equal to m.
ans = ans
+ (mp.ContainsKey(tmp) == false
? 0
: ((long)mp[tmp]));
// If this subarray has XOR equal to m itself.
if (xorArr[i] == m)
ans++;
// Add the XOR of this subarray to the map
if (mp.ContainsKey(xorArr[i]))
mp[xorArr[i]] = mp[xorArr[i]] + 1;
else
mp.Add(xorArr[i], 1);
}
// Return total count of subarrays having XOR of
// elements as given value m
return ans;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 4, 2, 2, 6, 4 };
int n = arr.Length;
int m = 6;
Console.Write(
"Number of subarrays having given XOR is "
+ subarrayXor(arr, n, m));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript Program to count all subarrays having
// XOR of elements as given value m with
// O(n) time complexity.
// Returns count of subarrays of arr with XOR
// value equals to m
function subarrayXor(aee,n,m)
{
let ans = 0; // Initialize answer to be returned
// Create a prefix xor-sum array such that
// xorArr[i] has value equal to XOR
// of all elements in arr[0 ..... i]
let xorArr = new Array(n);
// Create map that stores number of prefix array
// elements corresponding to a XOR value
let mp = new Map();
// Initialize first element of prefix array
xorArr[0] = arr[0];
// Computing the prefix array.
for (let i = 1; i < n; i++)
xorArr[i] = xorArr[i - 1] ^ arr[i];
// Calculate the answer
for (let i = 0; i < n; i++) {
// Find XOR of current prefix with m.
let tmp = m ^ xorArr[i];
// If above XOR exists in map, then there
// is another previous prefix with same
// XOR, i.e., there is a subarray ending
// at i with XOR equal to m.
ans = ans
+ (mp.has(tmp) == false
? 0
: (mp.get(tmp)));
// If this subarray has XOR equal to m itself.
if (xorArr[i] == m)
ans++;
// Add the XOR of this subarray to the map
if (mp.has(xorArr[i]))
mp.set(xorArr[i], mp.get(xorArr[i]) + 1);
else
mp.set(xorArr[i], 1);
}
// Return total count of subarrays having XOR of
// elements as given value m
return ans;
}
// Driver code
let arr=[4, 2, 2, 6, 4];
let n = arr.length;
let m = 6;
document.write("Number of subarrays having given XOR is "
+ subarrayXor(arr, n, m));
// This code is contributed by unknown2108
</script>
Producción
Number of subarrays having given XOR is 4
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Enfoque alternativo: uso del diccionario de Python para almacenar el prefijo XOR
Implementación:
C++
#include <bits/stdc++.h>
using namespace std;
//Function to return the XOR of all subarrays
int subarrayXor(int arr[], int n, int m)
{
//declaring the hashtable
//and initializing it with a count of 1
//for 0
unordered_map <int, int> HashTable;
HashTable[0] = 1;
int count = 0, curSum = 0;
for (int i = 0; i < n; i++)
{
curSum ^= arr[i];
if (HashTable[curSum ^ m] > 0)
count += HashTable[curSum ^ m];
HashTable[curSum]++;
}
return(count);
}
// Driver program to test above function
int main()
{
int arr[] = { 5, 6, 7, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 5;
//Function call
cout << "Number of subarrays having given XOR is " << subarrayXor(arr, n, m);
}
// This code is contributed by phasing17
Java
// Java program to implement the approach
import java.util.*;
class GFG
{
// Function to return the XOR of all subarrays
static int subarrayXor(int[] arr, int n, int m)
{
// declaring the hashtable
// and initializing it with a count of 1
// for 0
HashMap<Integer, Integer> HashTable
= new HashMap<>();
HashTable.put(0, 1);
int count = 0, curSum = 0;
for (int i = 0; i < n; i++) {
curSum ^= arr[i];
if (HashTable.containsKey(curSum ^ m))
count += HashTable.get(curSum ^ m);
if (!HashTable.containsKey(curSum))
HashTable.put(curSum, 0);
HashTable.put(curSum,
HashTable.get(curSum) + 1);
}
return (count);
}
// Driver program to test above function
public static void main(String[] args)
{
int[] arr = { 5, 6, 7, 8, 9 };
int n = arr.length;
int m = 5;
// Function call
System.out.println(
"Number of subarrays having given XOR is "
+ subarrayXor(arr, n, m));
}
}
// This code is contributed by phasing17
Python3
from collections import defaultdict
def subarrayXor(arr, n, m):
HashTable=defaultdict(bool)
HashTable[0]=1
count=0
curSum=0
for i in arr:
curSum^=i
if HashTable[curSum^m]:
count+=HashTable[curSum^m]
HashTable[curSum]+=1
return(count)
# Driver program to test above function
def main():
arr = [ 5, 6, 7, 8, 9 ]
n = len(arr)
m = 5
print("Number of subarrays having given XOR is "
, subarrayXor(arr, n, m))
if __name__ == '__main__':
main()
# This code is contributed by mrmechanical26052000
Javascript
<script>
// JavaScript program to implement the approach
// Function that calculates the number of subarrays
// with xor equal to given number
function subarrayXor(arr, n, m)
{
// declaring the HashTable object
var HashTable = {};
HashTable["0"] = 1;
var count = 0;
var curSum = 0;
// iterating over the array
for (var i of arr)
{
curSum ^= i;
// updating count if the xor of subarray is m
if (HashTable.hasOwnProperty((curSum ^ m).toString()))
{
count += HashTable[(curSum ^ m).toString()];
}
if (HashTable.hasOwnProperty((curSum).toString()))
HashTable[curSum.toString()] += 1;
else
HashTable[curSum.toString()] = 1;
}
return count;
}
// Driver Code
var arr = [ 5, 6, 7, 8, 9 ] ;
var n = arr.length;
var m = 5;
// Function Call
console.log("Number of subarrays having given XOR is ", subarrayXor(arr, n, m));
// This code is contributed by phasing17
</script>
Producción
Number of subarrays having given XOR is 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Anmol Ratnam . 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