Count subarrays with given XOR

Posted in

Count subarrays with given XOR
vinaykhatri

Vinay Khatri
Last updated on May 22, 2024

    Problem

    Given an array of integers, count the number of subarrays that have the XOR equal to ‘ x’.

    Sample Input

    [4, 2, 2, 6, 4]  ‘x’ = 6

    Sample Output

    4

    Explanation

    [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6] are the subarrays with XOR equal to 6

    Approach

    We can use hashmaps and prefix arrays to solve this problem. We first store the XOR of all the prefixes of the array in a separate array data structure. Create a map data structure to store the count of prefixes having given XOR value. Let xorArray store the XOR all prefixes of the input array.

    The intuition behind the approach is that if we are at current index j+1 , and xorArray[i]...xorArray[j] has the XOR value equal to ‘x’ , then xorArray[0]...xorArray[i-1] must be present in the prefix array, and the value should be equal to xorArray[j+1]^x We can use the below algorithm to solve this problem Traverse the array and for each element arr[i]:

    1. If the x^xorArray[i] is present in the map, increment the count of the answer with the value of the XOR
    2. If the current prefix is already on the map, increment the answer by 1
    3. At last, increment the current prefix’s value in the map by 1.

    Complexity Analysis

    The time complexity is O(N), and the space complexity is also O(N) due to the map

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    
    long long solve(int arr[], int n, int x)
    {
        long long ans = 0;
    
        int* xorArr = new int[n];
    
        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];
    
        // traverse the array
        for (int i = 0; i < n; i++) {
            // Find XOR of current prefix with x.
            int tmp = x ^ xorArr[i];
    
            // if the value of 'tmp' exists in map
            ans = ans + ((long long)mp[tmp]);
    
            // If this subarray has XOR equal to x itself.
            if (xorArr[i] == x)
                ans++;
    
            mp[xorArr[i]]++;
        }
    
        return ans;
    }
    
    int main()
    {
        int arr[] = { 4, 2, 2, 6, 4 };
        int n = sizeof(arr) / sizeof(arr[0]);
        int x = 6;
        cout << solve(arr, n, x);
    
        return 0;
    }

    Output

    4

    Java Programming

    import java.util.*;
    
    class Solution {
        static long solve(int arr[], int n, int x)
        {
            long ans = 0; // Initialize answer to be returned
    
            // to store prefixes XOR
            int[] xorArr = new int[n];
    
            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];
    
            // traverse the array
            for (int i = 0; i < n; i++) {
                // Find XOR of current prefix with x.
                int tmp = x ^ xorArr[i];
    
                // if the value if 'tmp' exists in the map
                ans = ans+ (mp.containsKey(tmp) == false? 0:((long)mp.get(tmp)));
    
                // If this subarray has XOR equal to x itself.
                if (xorArr[i] == x)
                    ans++;
    
                if (mp.containsKey(xorArr[i]))
                    mp.put(xorArr[i], mp.get(xorArr[i]) + 1);
                else
                    mp.put(xorArr[i], 1);
            }
    
            return ans;
        }
    
        public static void main(String[] args)
        {
            int arr[] = { 4, 2, 2, 6, 4 };
            int n = arr.length;
            int x = 6;
    
            System.out.print(solve(arr, n, x));
        }
    }

    Output

    4

    Python Programming

    def solve(arr, n, x):
        ans = 0 # Initialize answer
    
        # prefix array
        xorArr =[0 for _ in range(n)]
    
        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]
    
        # traverse the array
        for i in range(n):
            # Find XOR of current prefix with x.
            tmp = x ^ xorArr[i]
    
            # if the value of 'tmp' exists in the array
            if tmp in mp.keys():
                ans = ans + (mp[tmp])
    
            if (xorArr[i] == x):
                ans += 1
    
            mp[xorArr[i]] = mp.get(xorArr[i], 0) + 1
    
        return ans
    
    arr = [4, 2, 2, 6, 4]
    n = len(arr)
    x = 6
    
    print(solve(arr, n, x))

    Output

    4

    People are also reading:

    Leave a Comment on this Post

    0 Comments