Count even length subarrays having bitwise XOR equal to 0
Given an array arr[] of size N, the task is to count all possible even length subarrays having bitwise XOR of subarray elements equal to 0.
Examples:
Input: arr[] = {2, 2, 3, 3, 6, 7, 8}
Output: 3
Explanation:
Subarrays having XOR of elements equal to 0 are: {{2, 2}, {3, 3}, {2, 2, 3, 3}}
Therefore, the required output is 3.Input: arr[] = {1, 2, 3, 3}
Output: 1
Naive Approach: The simplest approach is to traverse the array and generate all possible subarrays. For each subarray, check if the length of the subarray is even and if the Bitwise XOR of the subarray elements is 0 or not. Follow the steps below to solve the problem:
- Initialize a variable, say res to store the count of subarrays that satisfy the given condition.
- Traverse the array and generate all possible subarrays.
- For each subarray, check if the length of the subarray is even and the bitwise XOR of their elements is 0, then increment the res by 1.
- Finally, print the value of res.
Below is the implementation of the above approach:
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> |
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved using Hashing. The idea is to store the frequency of the Prefix Xor in two separate arrays, say Odd[] and Even[], to store the frequency of the Prefix XOR of odd and even indices of the given array. Finally, print the count of all possible pairs from Even[] and Odd[] arrays having a value greater than or equal to 2. Following are the observations:
Odd Index – Odd Index = Even Length
Even Index – Even Index = Even LengthIf Even[X] ≥ 2: Bitwise XOR of all the elements between two even indices of the given array must be 0 and the length of the subarray is also an even number ( Even Index – Even Index ).
If Odd[X] ≥ 2: Bitwise XOR of all the elements between two odd indices of the given array must be 0 and the length of the subarray is also an even number ( Odd Index – Odd Index ).
Follow the steps below to solve the problem:
- Initialize two arrays, say Even[] and Odd[] to store the frequency of Prefix XOR at even and odd indices of the given array respectively.
- Initialize a variable, say cntSub, to store the count of subarrays that satisfy the given condition.
- Traverse the given array and compute the Prefix Xor of the given array.
- Store the frequency of Prefix XOR at even and odd indices of the given array in the arrays Even[] and Odd[] respectively.
- Finally, print the count of all possible pairs of Even[] and Odd[] having a value greater than or equal to 2.
Below is the implementation of the above approach:
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> |
3
Time Complexity: O(N)
Auxiliary Space: O(M), where M is the maximum bitwise XOR possible in all subarrays.
Contact Us