I stored indexes of elements of prefix array in seperate vectors with each element getting its own vector. Now for each vector that i got if the size of vector was more than 1 , it meant that element was present at atleast 2 places in prefix array. For all such vector iterate over them and for each index , ans = index * value_at_that_index - ( size of vector - index - 1 )* value_at_tht_index.
Thus in one iteration i was able to find distance between occurance of that element.
5 Likes
Thanks Sid.
You’re great. I am going to try implementing this in Java.
Although I thought using Hashmap in java but I couldn’t set up the formula to get the lengths when using a hashmap. 
1 Like
for(i = 1, i < k, i++) {
if(i > 1)
temp += (vv[i] - vv[i-1] - 1) * (i - 1) + (i - 2);
cnt += (vv[i] - vv[0] - 1) + temp;
}
This is what I’ve done.
See if this help.
1 Like
Yeah and dont forget to subtract n(n-1)/2 from this , as this is only giving distance between pairs , you have to subtract total number of pairs formed in oder to get number of triplets , as answer is lengthofsubarray - 1.
1 Like
Got it. Thanks man, really appreciate your efforts in explaining.
1 Like
Here is the explanation of this formula works :
Suppose an element is present at index 1 , 3 ,5 in prefix array.
So you want to find : (3- 1) + (5-1) + (5-3)
what do u see here , 1 is getting subtracted twice and added 0 times.
3 is getting subtacted once and added once.
5 is getting subtracted 0 times added twice.
So index*value - (n-index-1)*value.
7 Likes
https://www.codechef.com/viewsolution/25649739
the trick is-if the xor of elements of subarray of index starting from i and ends at k will be zero then u can find k-i triplets …now optimise the approach…also u can view my solution
1 Like
u can use a pair to store the numbers and the corresponding positions, then sort the array and maintain a frequency array. Now while counting the pairs to get all the permutations u will get a series (the positions need to be in ascending order for this).
My approach: CodeChef: Practical coding for everyone
Because when i==0 the value in the vector at 0 is 0 and the expression for calculating distance becomes 0 as we are doing multiplication with 0 . Hence to avoid that i guess.
See EG : 5 2 7
PREFIX ARRAY : 5 7 0
Now no elements are repeating so is answer 0 ? No right .
Thus if in prefix array we encouter 0 that means from index 0 till that index subarray is 0.( Length of subarray will be 3 hence ans+=v[i][j]{which is the index of 0 i.e 2 in this case}) . Final answer 2.
Hope this helps
@rakesh_54
3 Likes
Thanks a lot man ! understood it completely.
1 Like
In order to calculate the distance between the all pair you can keep track of index of last same element to find the current distance and the occurance of that element till now.
With basic hashing
It will go in just O (N) 
1 Like
I am describing tha same approach in different manner using Hashing in O (N) ; P
Firstly create the prefix XOR (let say A) and after that see the zero and the same elements in the array A and create a count variable equal to zero and increment the count variable by the number at which the zero comes and also increment the count variable for each equal elements.
Let say A = [1,2,0,3,1,4,0,1]
Count = 0
Count = (Count + 2 + 6)…(for the zero at index i ( as a first index equal to 0)
Now 1 and 0 are repeated
So first time the repeated element 1 is at the index 0 and second time is 4 so increment count variable by
Count = Count + absolute value of (4-(0+1))
Now for the third time 1 repeat so increment the count variable by seen from the starting time repetition
For ex
Count = Count + (7-(0+1))+(7-(4+1))
As the no of times number repeat the no of times the number add for addition in count variable this can be solved by dynamic programming, Same for the other repeated elements
Create an dictionary in which the keys are the repeated elements and their data is the array of 3 elements which is updated every time
So the first element is the index of that element , second element is the number of time it repeats and the third element is the number of the previous increment in the count variable…
This is little bit confusing
So see my solution in python in O(n)
https://www.codechef.com/viewsolution/25828488
can u please tell how did u get to that conclusion if xor=0 then no of triples =size of subarray -1 or was that merely an observation??
It’s a property of xor that a xor a = 0 , so from this you know first thing you got to do is find subarrays having xor 0. Now for such subarrays if xor is 0 that means there are i , j and ks such that xor i to j-1 = xor j to k only then we are getting final xor as 0. Now coming to your question how we can conclude length - 1. Take the example 4 3 5 2.
What all groups you can make going from left => 4=3^5^2 ; 4^3= 2^5 ; 4^3^5=2 (total 3)
Everytime you will be able to make only length -1 groups.
A(i) ^ A(I+1) ^ … ^ A(j-1) = A(j) ^…^A(k) .
Consider L.H.S as X , A(j) as Y, rest as Z
XOR X to both sides we get A(i) ^ … ^ A(k) =0
Now to get zero two elements must be same, if u get two elements at positions say i and k equal(k>i) …how many j can u choose i<j<=k?
Hope this helps. 
1 Like
thankx bro really helped a lot : )