Number of subarrays such that XOR of one half is equal to the other

0 0 7 minutes read

Given an array of N numbers, the task is to find the number of sub-arrays (size of the sub-array should be an even number) of the given array such that after dividing the sub-array in two equal halves, bitwise XOR of one half of the sub-array will be equal to bitwise XOR of the other half.

Examples:

Input : N = 6, arr[] = {3, 2, 2, 3, 7, 6}
Output : 3
Valid sub-arrays are {3, 2, 2, 3}, {2, 2}, 
and {2, 3, 7, 6}

Input : N = 5, arr[] = {1, 2, 3, 4, 5}
Output : 1

Input : N = 3, arr[] = {42, 4, 2}
Output : 0

Approach: If an array is divided into two equal halves and XOR of one half is equal to the other, it means that XOR of whole of the array should be 0, because A^A = 0. Now, to solve the above problem find the prefix XOR’s of all the elements of the given array starting from left.

Suppose, a sub-array starts from l and ends at r, then (r-l+1) should be even. Also, to find XOR of a given range (l, r) subtract prefix XOR at (l – 1) with prefix XOR at r.

Since, (r – l + 1) is even, hence, if r is even then l should be odd and vice versa. Now, divide your prefixes into two groups, one should be the group of prefixes of odd indexes and the other should be of even indexes. Now, start traversing the prefix array from left to right and see how many time this particular prefix A has already occurred in its respective group, i.e. prefixes at even indexes should be checked in even prefix group and prefixes at odd indexes in odd prefix group (because if r is even then (l-1) is also even, similar logic is applied if r is odd).

Below is the implementation of the above approach:

C++

// C++ program to find number of subarrays such that
// XOR of one half is equal to the other
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of subarrays such that
// XOR of one half is equal to the other
int findSubarrCnt(int arr[], int n)
{
    // Variables to store answer and current XOR's
    int ans = 0, XOR = 0;
 
    // Array to store prefix XOR's
    int prefix[n];
 
    for (int i = 0; i < n; ++i) {
 
        // Calculate XOR until this index
        XOR = XOR ^ arr[i];
 
        // Store the XOR in prefix array
        prefix[i] = XOR;
    }
 
    // Create groups for odd indexes and even indexes
    unordered_map<int, int> oddGroup, evenGroup;
 
    // Initialize occurrence of 0 in oddGroup as 1
    // because it will be used in case our
    // subarray has l = 0
    oddGroup[0] = 1;
 
    for (int i = 0; i < n; ++i) {
 
        if (i & 1) {
 
            // Check the frequency of current prefix 
            // XOR in oddGroup and add it to the 
            // answer
            ans += oddGroup[prefix[i]];
 
            // Update the frequency
            ++oddGroup[prefix[i]];
        }
        else {
 
            // Check the frequency of current prefix 
            // XOR in evenGroup and add it to the
            // answer
            ans += evenGroup[prefix[i]];
 
            // Update the frequency
            ++evenGroup[prefix[i]];
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int N = 6;
 
    int arr[] = { 3, 2, 2, 3, 7, 6 };
 
    cout << findSubarrCnt(arr, N);
 
    return 0;
}

Java

// JAVA program to find number of subarrays such that
// XOR of one half is equal to the other
import java.util.*;
 
class GFG
{
         
    // Function to find number of subarrays such that
    // XOR of one half is equal to the other
    static int findSubarrCnt(int arr[], int n)
    {
        // Variables to store answer and current XOR's
        int ans = 0, XOR = 0;
     
        // Array to store prefix XOR's
        int prefix[] = new int[n];
     
        for (int i = 0; i < n; ++i) 
        {
     
            // Calculate XOR until this index
            XOR = XOR ^ arr[i];
     
            // Store the XOR in prefix array
            prefix[i] = XOR;
        }
     
        // Create groups for odd indexes and even indexes
        HashMap<Integer, Integer> evenGroup = new HashMap<>();
        HashMap<Integer, Integer> oddGroup = new HashMap<>();
         
 
        // Initialize occurrence of 0 in oddGroup as 1
        // because it will be used in case our
        // subarray has l = 0
        oddGroup.put(0, 1);
     
        for (int i = 0; i < n; ++i) 
        {
     
            if (i % 2== 1) 
            {
     
                // Check the frequency of current prefix 
                // XOR in oddGroup and add it to the 
                // answer
                if(oddGroup.containsKey(prefix[i]))
                {
                    ans += oddGroup.get(prefix[i]);
     
                    // Update the frequency
                    oddGroup.put(prefix[i],oddGroup.get(prefix[i] + 1));
                }
                else
                {
                    oddGroup.put(prefix[i], 1);
                }
                 
            }
            else
            {
     
                // Check the frequency of current prefix 
                // XOR in evenGroup and add it to the
                // answer
                if(evenGroup.containsKey(prefix[i]))
                {
                    ans += evenGroup.get(prefix[i]);
     
                    // Update the frequency
                    evenGroup.put(prefix[i],evenGroup.get(prefix[i] + 1));
                }
                else
                {
                    evenGroup.put(prefix[i], 1);
                }
            }
        }
     
        return ans;
    }
     
    // Driver Code
    public static void main (String[] args) 
    {
     
        int arr[] = { 3, 2, 2, 3, 7, 6 };
        int N = arr.length;
     
        System.out.println(findSubarrCnt(arr, N));
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 program to find number of subarrays 
# such that XOR of one half is equal to the other 
 
# Function to find number of subarrays 
# such that XOR of one half is equal 
# to the other 
def findSubarrCnt(arr, n) :
     
    # Variables to store answer
    # and current XOR's 
    ans = 0; XOR = 0; 
 
    # Array to store prefix XOR's 
    prefix = [0] * n; 
 
    for i in range(n) : 
 
        # Calculate XOR until this index 
        XOR = XOR ^ arr[i]; 
 
        # Store the XOR in prefix array 
        prefix[i] = XOR; 
     
    # Create groups for odd indexes and 
    # even indexes 
    oddGroup = dict.fromkeys(prefix, 0) 
    evenGroup = dict.fromkeys(prefix, 0)
 
    # Initialize occurrence of 0 in oddGroup 
    # as 1 because it will be used in case  
    # our subarray has l = 0 
    oddGroup[0] = 1; 
 
    for i in range(n) :
 
        if (i & 1) :
 
            # Check the frequency of current 
            # prefix XOR in oddGroup and add 
            # it to the answer 
            ans += oddGroup[prefix[i]]; 
 
            # Update the frequency 
            oddGroup[prefix[i]] += 1; 
         
        else : 
 
            # Check the frequency of current 
            # prefix XOR in evenGroup and add 
            # it to the answer 
            ans += evenGroup[prefix[i]]; 
 
            # Update the frequency 
            evenGroup[prefix[i]] += 1; 
 
    return ans; 
 
# Driver Code 
if __name__ == "__main__" : 
 
    N = 6; 
 
    arr = [ 3, 2, 2, 3, 7, 6 ]; 
 
    print(findSubarrCnt(arr, N)); 
 
# This code is contributed by Ryuga

C#

// C# program to find number of subarrays such that
// XOR of one half is equal to the other
using System;
using System.Collections.Generic; 
 
class GFG
{
         
    // Function to find number of subarrays such that
    // XOR of one half is equal to the other
    static int findSubarrCnt(int [] arr, int n)
    {
        // Variables to store answer and current XOR's
        int ans = 0, XOR = 0;
     
        // Array to store prefix XOR's
        int [] prefix = new int[n];
     
        for (int i = 0; i < n; ++i) 
        {
     
            // Calculate XOR until this index
            XOR = XOR ^ arr[i];
     
            // Store the XOR in prefix array
            prefix[i] = XOR;
        }
     
        // Create groups for odd indexes and even indexes
        Dictionary<int, int> evenGroup = new Dictionary<int, int>();
        Dictionary<int, int> oddGroup = new Dictionary<int, int>();
 
        // Initialize occurrence of 0 in oddGroup as 1
        // because it will be used in case our
        // subarray has l = 0
        oddGroup[0] = 1;
     
        for (int i = 0; i < n; ++i)
        {
     
            if (i % 2== 1)
            {
     
                // Check the frequency of current prefix 
                // XOR in oddGroup and add it to the 
                // answer
                if(oddGroup.ContainsKey(prefix[i]))
                {
                    ans += oddGroup[prefix[i]];
     
                    // Update the frequency
                    oddGroup[prefix[i]]++;
                }
                else
                {
                    oddGroup[prefix[i]] = 1;
                }
                 
            }
            else
            {
     
                // Check the frequency of current prefix 
                // XOR in evenGroup and add it to the
                // answer
                if(evenGroup.ContainsKey(prefix[i]))
                {
                    ans += evenGroup[prefix[i]];
     
                    // Update the frequency
                    evenGroup[prefix[i]]++;
                }
                else
                {
                    evenGroup[prefix[i]] = 1;
                }
            }
        }
     
        return ans;
    }
     
    // Driver Code
    public static void Main () 
    {
     
        int [] arr = { 3, 2, 2, 3, 7, 6 };
         
        int N = arr.Length;
     
        Console.WriteLine(findSubarrCnt(arr, N));
    }
}
 
// This code is contributed by ihritik

Javascript

<script>
 
// Javascript program to find number of subarrays such that
// XOR of one half is equal to the other
      
    // Function to find number of subarrays such that
    // XOR of one half is equal to the other
    function findSubarrCnt(arr, n)
    {
        // Variables to store answer and current XOR's
        let ans = 0, XOR = 0;
       
        // Array to store prefix XOR's
        let prefix = Array.from({length: n}, (_, i) => 0);
       
        for (let i = 0; i < n; ++i) 
        {
       
            // Calculate XOR until this index
            XOR = XOR ^ arr[i];
       
            // Store the XOR in prefix array
            prefix[i] = XOR;
        }
       
        // Create groups for odd indexes and even indexes
        let evenGroup = new Map();
        let oddGroup = new Map();
           
   
        // Initialize occurrence of 0 in oddGroup as 1
        // because it will be used in case our
        // subarray has l = 0
        oddGroup.set(0, 1);
       
        for (let i = 0; i < n; ++i) 
        {
       
            if (i % 2== 1) 
            {
       
                // Check the frequency of current prefix 
                // XOR in oddGroup and add it to the 
                // answer
                if(oddGroup.has(prefix[i]))
                {
                    ans += oddGroup.get(prefix[i]);
       
                    // Update the frequency
                    oddGroup.set(prefix[i],oddGroup.get(prefix[i] + 1));
                }
                else
                {
                    oddGroup.set(prefix[i], 1);
                }
                   
            }
            else
            {
       
                // Check the frequency of current prefix 
                // XOR in evenGroup and add it to the
                // answer
                if(evenGroup.has(prefix[i]))
                {
                    ans += evenGroup.get(prefix[i]);
       
                    // Update the frequency
                    evenGroup.set(prefix[i],evenGroup.get(prefix[i] + 1));
                }
                else
                {
                    evenGroup.set(prefix[i], 1);
                }
            }
        }
       
        return ans;
    }
       
    // Driver code
     
        let arr = [ 3, 2, 2, 3, 7, 6 ];
        let N = arr.length;
       
        document.write(findSubarrCnt(arr, N));
                     
</script>

Output:

Time Complexity: O(N), where N is the size of the given input array.
Auxiliary Space: O(N), where N is the size of the given input array.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!