Reader, we discuss the approach by considering the following scenario.
We are given the input array as [a,b,c,d,e,f]. Two pointers p1 and p2 are taken. This p1 moves in the outer loop and p2 moves in the inner loop.
We assume that at the current instance, p1 points to b and p2 points to e. We calculate b^c^d^e. Let this value come out to be 0 i.e. b^c^d^e=0.
Now we place 'i' at b and 'k' at e. We see that since i< j<=k,therefore, j can be placed at either 'c' or 'd' or 'e'.
We represent the elements in sets X and Y as X-Y. So, the sets are as follows if j is placed on:
- c : b-cde
- d : bc-de
- e : bcd-e
Reader, meditate on the fact that since b^c^d^e=0 and XOR cancels out duplicate elements, therefore in the above 3 cases, b=cde , bc=de and bcd=e.
If you are not able to understand this fact, we prove it using the example given below.
In this example, the array given to us is [5,6,2,3,3,5,3,2,5,3,8,9].
We place 'i' on 2 and 'k' on 3 and get 2^3^3^5^3^2^5^3=0. Since, i< j< =k, therefore, j can point to any of the bulleted elements.
In figure 2, the sets X-Y can be seen for all the elements 'j' can point on.
If 'j' pointed to the element at index 3, with a value of 3, then the set would been:
Remember that we cancel all the duplicates when we apply XOR as shown in figure 2, which is why we are left with 2-2 is. Here X=Y. Hence we obtain one of our desired answers.
Reader, we want you to try this for the other sets too. They all fulfill X=Y.
If you have understood the approach, then writing its code is quite simple.