For context, link to the problem being discussed.

Solution that passes

  • Let’s say X=e1e2enX = e_1\oplus e_2\oplus\cdots \oplus e_n i.e. XOR of all elements of SS. If it satisfies the condition of being kk then it is the answer, otherwise no answer exists.

Why is it so?

  • One thing is for sure that every element will be mapped to some other element in the set.

  • If the answer is kk then aia_i will be mapped to aika_i\oplus k. So what we can do is we can check to which element, first element of the set will be mapped, i.e. try every possible pair with first element and check if so formed kk is the answer. Mind that kk will always be positive as there is no repetition in a set.

  • This approach can be slow because one pass for every pair and there are N1N-1 pairs, where NN is size of the set.

  • Before optimizing this solution, I want to prove why any kk that keeps the set unchanged will be the answer.

  • Let’s say a1a2a_1 \oplus a_2 is kk thus a1a_1 is mapped to a2a_2. Now there are N2N-2 remaining elements, which can be divided into (N2)/2(N-2)/2 or we should say N/21N/2 - 1pairs with XOR kk. As given in the problem statement N/2N/2 is odd then N/21N/2-1 is even. We know that if same number is XORed even times it becomes 00. So XOR of all elements is kk. Thus whatever you do this will remain constant because set is unchanged and it guarantees that at most one valid mapping exists.

  • Now you know why the solution stated above i.e. take XOR of all elements if it satisfies the condition then it is the answer. It is minimum because it is the only answer.

Corner case

  • There can be created many corner cases such that XX is zero for the set. No such case is included on the judge. Even authors solution fails this, but it is trivial (no nitpicking), but testers solution doesn’t fail this test :). For example:
1
6
17 3 2 4 12 24