Lets take an example 5 2 7 7 7 7 7 7 5.
prefixXorArray = 5 7 0 7 0 7 0 7 2.
only considering cases where prefix xor is 0
That is index 2,4,6.
The reason you directly add index is because when a prefixXor is 0 directly it would mean that from the start of the array to that index we get a subarray that has xor equal to 0.
So we can choose triplets (o,j,index).
ie- (0,j,2) , (0,j,4) , (0,j,6)
These triplets would not be considered when we consider distance between pairs in prefixXorArray because at that time we are considering the subarray from m to n where prefixXor[m] = prefixXor[n] = 0. whereas prefixXor[0] would be equal to a[0] the first element.
So in case of 0 in the prefix XOR array there is no need for me to calculate the distances of pairs since 0 xor of sub-array is formed only @ index. Its clear now.
But why do we need to subtract the ans from the total no of pairs formed by the sub-arrays ?
Sorry i guess i was not that clear. You need to calculate distance of pairs even. since in the example stated by me before
5 2 7 7 7 7 7 7 5.
prefixXorArray = 5 7 0 7 0 7 0 7 2.
only considering cases where prefix xor is 0
That is index 2,4,6.
There are basically 2 cases.
1st indexes where prefixXor are equal those index’s could be used to get a subbarray whose xor is 0 and 2nd When prefixXor is 0 then at time the complete array till the index would itself be a subarray that has xor =0.
now case when prefixXor is 0. (indexes 2,4,6)
from 2nd case we need to add the index directly to get count of triplets. (not going into how this is giving count, i’d suggest to read the editorial once it comes). and since at index’s 2 and 4 both have same prefixXor we would also get a subarray between them.
basically the questions breaks down to the following :-
if for any i,j a[i]^a[i+1]^…^a[j] = 0 then triplets i,k,j can be formed which satisfy the condition. and since i<k<=j. for a given i,j possible values of k can be j-i-1.
so we need to calculate all i,j where subbarray xor is 0.
after getting all i,j we just need to calculate the number of possible k for each i,j and that would give us the answer.
suppose a prefixXor value of 5 occurs at indexes 2,6,8. then possible i,j pairs are (2,6) , (2,8) , (6,8). and then for each of these pairs you would need to calculate the number of possible values of k which would give you the number of triplets. But this method of calculation would give you tle since actually getting the pairs i,j from the list of indexs would be costly.
So to further optimize we need to notice that what we need is basically j-i-1 for each j>i and this calculation can be done in linear time.
Notice number of triplets are j-i-1. this ‘-1’ would occur basically for every pair. so number of times ‘-1’ would occur would be equal to number of different pairs formed (i,j). This number would be (number of possible choices for i,j)C2. which in your case is SizeC2 or Size*(Size-1)/2.
U can create a prefix XOR array, prefix[i] = a1 ^ a2 ^ … ^ ai.
Then, ai ^ … ^ a(j - 1) is prefix[j - 1] ^ prefix[i - 1]
aj ^ … ^ ak = prefix[k] ^ prefix[j - 1]
Since these have to be equal therefore prefix[i - 1] = prefix[k].
So fix j and count these pairs by using a map.
Complexity is O(NlogN).
