Last Updated: 15 Apr, 2021

Xor Equal Triplets

Moderate

Asked in company

Solve now

Problem statement

You are given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the number of triplets (i, j, k), where ‘i’, ‘j’, ‘k’ are three indices of ‘ARR’ such that -:

1. 0 <= ‘i’ < ‘j’ <= ‘k’ < ‘N’ .

2. ARR[i] ^ ARR[i + 1] ^ ... ^ ARR[j - 1] = ARR[j] ^ ARR[j + 1] ^ ... ^ ARR[k] i.e bitwise xor of all integers in subarray of ‘ARR’ between index ‘i’ and ‘j-1’ inclusive, should equals to bitwise xor of all integers in subarray of ‘ARR’ between index ‘j’ and ‘k’ inclusive.

Note:

1. Consider 0 based indexing in ‘ARR’.
2. Symbol ^ denotes the bitwise-xor operation.
3. Xor of subarray having a single integer is that integer itself.
4. It is guaranteed that the number of such triples fit in a 32 bit integer.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’, representing the size of ‘ARR’ 

The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘ARR’.

Output Format:

For each test case, print a single integer that represents the number of such triplets.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 50
2 <= N <= 10000
1 <= ARR[i] <= 2^31 - 1

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to initialize ‘COUNTER’:= 0 and then one by one try out all possible ways of selecting three indices, if for any triplet (i, j, k), Xor of subarray ‘ARR[i:j-1]’ equal Xor of subarray ‘ARR[j:k]’, then increment ‘COUNTER’ by 1.

The steps are as follows:

Initialize an integer variable ‘COUNTER’:= 0.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
1. Initialize an integer variable ‘SUBXOR1’: = 0.
2. Run a loop where ‘j’ ranges from ‘i’+1 to ‘N’-1 and for each ‘j’ do the following -:
  1. Do ‘SUBXOR1’:= ‘SUBXOR1’ ^ ‘ARR[j-1]’, where ^ is bitwise xor operation. Note ‘SUBXOR1’ has xor of all integers of subarray ARR[i:j-1].
  2. Initialize an integer variable ‘SUBXOR2’: = 0.
  3. Run a loop where ‘k’ ranges from ‘j’ to ‘N’-1 and for each ‘k’ do the following -:
    1. Do ‘SUBXOR2’:= ‘SUBXOR2’ ^ ‘ARR[k]’. Note ‘SUBXOR2’ has xor of all integers of subarray ‘ARR[j:k]’.
    2. If ‘SUBXOR1’ = ‘SUBXOR1’, then increment ‘COUNTER’ by 1.
Return ‘COUNTER’.

Solve now

02 Approach

The basic idea is based on the fact that xor of two equal integers is 0 and two integers are equal if their xor is 0. So, we can say for any triplet (i, j, k) such that 0 <= ‘i’ < ‘j’ <= ‘k’ < ‘N’ and ‘ARR[i]’ ^ ‘ARR[i + 1]’ ^ ... ^ ‘ARR[j - 1]’ = ‘ARR[j]’ ^ ‘ARR[j + 1]’ ^ ... ^ ‘ARR[k]’ , then ‘ARR[i]’ ^ ‘ARR[i + 1]’ ^ ... ‘ARR[k]’ = 0, i.e xor of all integer in subarray ‘ARR[i:k]’ is 0.

For any subarray ‘ARR[i:k]’ if xor of its all elements is 0, then for any integer ‘j’ such that ‘i’ < ‘j’ <= ‘k’, we can say, xor of all elements of subarray ‘ARR[i:j-1]’ equals xor of all elements of subarray ‘ARR[j:k]’, that means every such pair (‘i’ , ‘k’) can split in ‘k-i’ valid triplets (‘i’ , ‘i+1’ , ‘k’), (‘i’ , ‘i+2’ , ‘k’) .. (‘i’ , ‘k-1’ , ‘k’), (‘i’ , ‘k’ , ‘k’). Thus the problem reduces to identifying all subarrays having xor 0 and the answer will be the sum of the length of all such subarrays., we can easily find all such subarrays in O(N^2) times.

The steps are as follows:

Initialize an integer variable ‘COUNTER’:= 0.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
1. Initialize an integer variable ‘SUBXOR’: = ‘ARR[i]’.
2. Run a loop where ‘j’ ranges from ‘i’+1 to ‘N’-1 and for each ‘j’ do the following -:
  1. Do ‘SUBXOR’:= ‘SUBXOR1’ ^ ‘ARR[j]’, where ^ is bitwise xor operation. Note ‘SUBXOR’ has xor of all integers of subarray ‘ARR[i:j]’.
  2. If ‘SUBXOR’ = 0, then do ‘COUNTER’ := ‘COUNTER’ + ‘j’ - ‘i’.
Return ‘COUNTER’.

Solve now

03 Approach

As discussed in the previous approach, we need to find all such pair (i, k) such that xor of all integers of subarray ‘ARR[i:k]’ is 0 i.e ‘ARR[i]’ ^ ‘ARR[i+1]’ ^...^ ‘ARR[k]’ = 0 and answer will be the sum of ‘k-i’ for each such pair.

To find out the pairs (‘i’ , ‘k’) that satisfy ‘ARR[i]’ ^ ‘ARR[i+1]’ ^...^ ‘ARR[k]’ = 0, we can use a map to store the xor of prefixes, and when xor of two prefixes are equal, like ‘ARR[0]’ ^ ‘ARR[1]’ ^...^ ‘ARR[i-1]’ = ‘ARR[0]’ ^ ‘ARR[1]’ ^...^ ‘ARR[k]’, we can conclude that (‘ARR[0]’ ^ ‘ARR[1]’ ^...^ ‘ARR[i-1]’ ) ^ (‘ARR[0]’ ^ ‘ARR[1]’ ^...^ ‘ARR[k])’ = ‘ARR[i]’ ^ ‘ARR[i+1]’ ^...^ ‘ARR[k]’ = 0. In other words, xor of all integers of subarray ‘ARR[i:j]’ will be 0 if xor of all integers of prefix ‘ARR[0:i-1]’ and prefix ‘ARR[0:j]’ is equal.

If we check the prefixes with the same xor-sum every time, then the time complexity is O(N^2), However, because only the sum of starts of the prefixes and the number of prefixes are important, we can optimize the solution to O(N) using Hashmap as described below.

The steps are as follows:

Initialize an integer variable ‘COUNTER’:= 0.
Create a Hash Map ‘COUNTIND’ where ‘COUNTIND’ has an integer key mapped with a value which is the number of prefix having prefix xor equals to key.
Create another Hashmap ‘SUMIND’ where ‘SUMIND’ has an integer key mapped with a value which is the sum of starts of the prefix having prefix xor equals to key.
Initially in both hash maps, do ‘COUNTIND[0]’ = 1 and ‘SUMIND[0]’ = 0.
Initialize an integer variable ‘PREXOR’: = 0.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
1. Do ‘PREXOR’: = ‘PREXOR’ ^ ‘ARR[i]’.
2. If key ‘PREXOR’ is present in Hashmap ‘COUNTIND’ then do ‘COUNTER’ += ‘i’ * ‘COUNTIND[PREXOR]’ - ‘SUMIND[PREXOR]’.
3. Do ‘COUNTIND[PREXOR]’ += 1.
4. Do ‘SUMIND[PREXOR]’ += i + 1.
Return ‘COUNTER’.

Solve now