@suyashd95
Lol, firstly no need to feel so down just because of this Q. Listen dude, this Q is VERY GOOD in hiding the real trick. The thing which this Q tested was apt/clever reading of Q, not your concepts of coding.
Ask yourself, âWhat is the question asking me?â
The question here says (or rather claims to) ask for the permutation of shortest path. But is it REALLY asking that?
The output says to print the XOR of the permutation you found.
Note 1- The permutation which we âfoundâ goes through all the points given, and is the shortest path.
The question now asks you to print the XOR of the permutation. Let me stress again, the permutation consists of/goes through all the points given in input.
Got hint?
Well, I know you wouldnât, so let me tell you how the problem setter trolled us.
What is 2+3+5?
10âŚ
Ok, what is 3+2+5?
10 againâŚ
What is 5+3+2??
10 againâŚ
The questionâs answer is also like that. The question asks us XOR of the permutation. And that permutation has all the points given in the input.
Meaning, speaking in more detail-
Let points given as input be p1, p2, p3 ,p4 ,p5.
Let Shortest permutation be p5, p4, p2, p1, p3.
What is the output asking us?
(Please assume that â+â = XOR for below. )
Its asking for p5+p4+p2+p1+p3
Lets re-arrange it-
Let p3+p5+4 =V
Since-
V= p3+p5+p4 = p4+p5+p3 = p3+p4+p5 (meaning, any permutation of them are equal) &etc. we can re-arrange it in any way we want(since XOR is commutative).
[Please pay close attention to what I concluded above. if p3+p5+p4 is equal to V, then ANY combination of them is equal to V]
Now I think, you would agree that if we can re-arrange p5+p4+p2+p1+p3 in any way we want, then you will find that we can also re-arrange it as-
p1+p2+p3+p4+p5
And this is nothing but the order of input given.
Infact, even order of input doesnât matter. As i said with norma + operation, 2+3+5 is 10 in ANY order. Exact same rule applies to XOR also!
Meaning, once inputted all the points, all you need to return is the XOR of all the points. THATS ALL.
If the value of XOR of all points is V1, then it doesnât matter what order you XORâed them, it doesnât matter if the order you XORâed them is the âshortest pathâ or any random combination, the value is SAME!
The problem setter trolled us by the fact that, while everyone was busy finding the shortest distance, many failed to realize that since 2+3+5 = 10 irrespective of permutation, the answer is actually just asking them the XOR of all the points in any combination possible.
Role of XOR-
The role of XOR is that, it is the thing which makes the Q a troll.
Had he actually asked the shortest permutation , the Q would have indeed been wayyy tougher.
And had the problem setter asked something like âGive the sum of X and Y co-ordinates of all points of shortest permutation which visits every point onceâ or something on that line, then everyone would have found the trick.
Since they used âXORâ, people werenât able to see through the problem setterâs intention immediately. It took them a lot of ranting and head scratching (which must have highly amused the problem setter- I may remark!) before they were finally like âHOLYYY GODD! THE Q WAS JUST ASKING FORâŚ!!!â
Long story short- XOR was best option among available operators to misguide people. XD