title: 'Leetcode 1442' topic : 'leetcode' id: 1 description: 'Leetcode medium problem. leetcode problem of the day' subtopic: ['']

Count Triplets That Can Form Two Arrays of Equal XOR

Leetcode - 1442 [Count Triplets That Can Form Two Arrays of Equal XOR]

🧑🏽‍💻 Problem statement

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let's define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example :

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Note :-

This is a quite interesting problem, also it is a Leetcode medium problem. This problem has 2 approaches to solve, one with O(n^2) time complexity and other with O(n) time complexity. The later is quite hard to understand, but i will try my best to explain.

O(n^2) solution Intuition :-

Here the aim is to find the number of triplets i,j,k where i is less than j and j is less than equal to k and xor of elements from i to j-1 equal to xor of elements from j to k.
There are some things to notice here, here i and k are the boundaries for the sub array, and the number of element is it should be greater than or equal to 2.
Another point to note is xor has an interesting property that the xor of same number is 0 (a^a=0). that means we are asked to find out sub array with xor of all the elements equal to 0.
Now the problem gets easier, as we can consider all the sub arrays and find the number of subarrays with xor of all elements equal to 0.
But is the number of subarrays with all elements whose xor equal to 0 the result? NO!! when we find a subarray with xor of all elements equal to 0, what we actually found is upper and lower bound (ie i and k), we can place j in between i and k (including j excluding i). That can be done in length of subarray - 1 times (ie excluding the position of i).
Length of subarray is upper bound - lower bound +1, hence we will add upper bound - lower bound.

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int cnt=0;
        int n = arr.size();
        for(int i=0;i<n;i++){
            int exor =0; 
            for(int j=i;j<n;j++){
               exor=exor^arr[j];
               if(exor==0) {
                cnt+=j-i;}
            }
        }
        return cnt;
    }
};

O(n) solution Intuition :-

As we discussed earlier xor has an interesting property that the xor of same number is 0 (a^a=0). that means we are asked to find out sub array with xor of all the elements equal to 0.
That is while traversing the array at every index we can store every prefix xor and the count in a unordered map called prefix_cnt . with this map we can determine weather a particular prefix xor is previously encountered. if it is encountered that means some elements in between xor up to 0. ie, if we remove the elements from 0 till the previously encountered index from the current subarray, the remaining elements would xor up to zero.
the map will be initialized with prefix_cnt[0]=1. you will get to know why this latter.
But how would we count the number of sub arrays?, since we are only storing prefix xor and its corresponding count.
Hence we will store the indexes for a particular prefix xor in another unordered map called prev_prefix_index (There is a catch here, which we will discuss below).
Now we have index for a particular prefix xor ,what will we add to the count? we will add current index - previous prefix index -1, which can be also written as current index - (previous prefix index + 1).
Hence while storing previous prefix index for a particular prefix we would store index+1.
As far as now its all good. but we have not considered the presence of multiple same prefixes. Obviously we would increase the count of that prefix in prefix_cnt map. but what about prev_prefix_index? we will understand it through an example below -

Input: arr = [1,1,1,1,1]
Output: 10

The corresponding prefix xor of the array is [1,0,1,0,1]

Now consider we are at index 4, where the prefix is 1. here we have encountered same prefix in 2 previous indexes (index 0 and index 2). how many valid subarrays will be there ending at index 4, one is the sub array neglecting all element till index 2 from starting, and other will be subarray neglecting index 0.
The current index i is 4. so what will we add to count? as we saw earlier we would add the size of sub array -1 to count, ie we would add (4-(2+1)) and (4-(0+1)). which can be written as 4+4 -(2+1+3+1) that can be written as i*prefix_cnt[prefix] - sum of indexes of that prefix.
That is why we added 1 while storing prev prefix index. and also we would store the index sum of a particular prefix in prev prefix index.

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n=arr.size();
        unordered_map<int,int>prefix_cnt;
        unordered_map<int,int>prev_prefix_index;
        prefix_cnt[0]=1;
        int prefix=0;
        int cnt=0;

        for(int i=0;i<n;i++){
            prefix^=arr[i];
            if(prefix_cnt.find(prefix)!=prefix_cnt.end()){
                cnt+=i*prefix_cnt[prefix]-prev_prefix_index[prefix];
            }
            prefix_cnt[prefix]++;
            prev_prefix_index[prefix]+=i+1;
        }
        return cnt;
    }
};