Count subarrays with given XOR

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:

• Modular Exponentiation in Logarithmic Time
• Delete Nodes And Return Forest
• Longest Consecutive Sequence in Linear time
• Minimum Edit Distance
• Majority Element
• Merge Two Sorted Arrays in-place
• Longest subarray with sum as K
• Rearrange an array in maximum minimum form
• Rod Cutting Problem
• Program to Rotate an Array