Subarray with given XOR

Problem Link

Given an array of integers A and an integer B Find the total number of subarrays having bitwise XOR of all elements equal to B.

Brute force approach

An easy approach is to find all the subarrays, perform XOR operations to compare them with the target value B, and then count the answers. This process requires two loops to obtain subarrays.

public class Solution {
    public int solve(ArrayList<Integer> A, int B) {
        int ans = 0;

        for(int i=0; i<A.size(); i++){
            int acc_xor = 0;
            for(int j=i; j<A.size(); j++){
                acc_xor = acc_xor ^ A.get(j);
                if(acc_xor==B) ans+=1;
            }
        }
        return ans;
    }
}

Optimal Solution

XOR Properties

Bitwise xor has the following 3 important properties.

a ^ 0 = a

If a ^ b = c then b ^ c = a and c ^ a = b

a ^ a = 0

Xor is denoted by the caret symbol ^

Intuition

1. Calculate the xor at each index.

2. xor at index i is xor[0->i] = nums[0] ^ nums[1] ^ nums[2] ^ ......^ nums[i]

3. For subarray nums[i]....nums[j] the xor value xor[i->j] = xor[i-1] ^ xor[j] because the elements in the left half will get canceled since xor of the same elements results in 0.

Following is the xor value of each array on the right

Code

Store the accumulated XOR value in the hashmap and count its occurrences. If the XOR value at a particular index 'i' is the same as the target value, then increment the answer. Another scenario involves subarrays that end at index 'i' and also have the XOR value equal to the target value. To find this subarray, perform the bitwise XOR of the target and accumulated XOR value. Check whether you have encountered the resulting XOR value in the map. If yes, then add this count to your answer.

public class Solution {
    public int solve(ArrayList<Integer> A, int B) {
        int ans = 0;
        Map<Integer, Integer> dict = new HashMap<>();

        int acc_xor = 0;

        for(int i=0; i<A.size(); i++){
            acc_xor = acc_xor ^ A.get(i);
            if(acc_xor==B) ans+=1;
            int opp = acc_xor ^ B;
            if(dict.containsKey(opp)){
                ans+=dict.get(opp);
            }
            if(!dict.containsKey(acc_xor))
                dict.put(acc_xor,0);
            int val = dict.get(acc_xor);
            dict.put(acc_xor,val+1);
        }
        return ans;
    }
}