@vijju123 First of all, thank you for so much answering my questions… Thankfully, I got my groove back after writing my question by listening to Kishore Kumar’s hits as well as solving a couple of other practice questions…
Your explanation was absolutely wonderful and it cleared all of my misconceptions and doubts regarding this fantastic question…
Even though, I am sure that my doubts are all gone… Yet, to verify, that I am finally thinking along the correct lines, I am putting forward my own test case…
Input:
4
2 3
1 2
9 0
0 0
In the above input, the only thing which matters is the number of points which, in the above case is, 4.
The coordinates of individual points really does not count, since they are present to confuse us… Hence, they do not play any role in the algorithm to find the correct answer. So, we can safely ignore them.
Output:
4
The answer is based on the fact that final answer (A)= 1 XOR 2 XOR 3 XOR 4 = 4. It is based on the fact that we have marked each point in a sequential order. Hence:
2 3 -> 1
1 2 -> 2
9 0 -> 3
0 0 -> 4
Multiple permutations can exist which will lead to shortest path, like [1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 3, 2, 1]… Each permutation will end up having the same result since XOR operation is commutative in nature.
So, coming to the final output…
We can easily calculate the final answer by XORing each mark i.e, equation A.
Steps:
- Initially, A = 1 (Since, 0 XOR 1 = 1)
- A = 1 XOR 2 = 3
- A = 3 XOR 3 = 0
- A = 0 XOR 4 = 4
Hence, the final output: 4… Please do me a favor and tell me whether my output is indeed the right one depending on my input…
