I noticed that some accepted solutions to this problem (XORGM) fail on a certain test case
1
2
3 13
10 4
The output should (as I understand the question to be) be 4 10 since 3 xor 4 == 13 xor 10 == 7
But some of the accepted solutions give -1
Did I understand the question wrong or is my concern valid? Is there any other way I should raise awareness about this if my concern is valid?
Read the question again. N is always odd
Ah. Okay then. Can’t believe I missed that
Can someone explain the significance of having N always odd?
Yeah, I missed that point (insignificant it might seem at first) that N is odd. However it is the key in solving the problem.
When N is odd, X^X^X…(n times) = X. Therefore the value of our “constant” is (A1^A2^…AN)^(B1^B2^…BN)
1 Like
Here is my code which works for N = even also
https://www.codechef.com/viewsolution/29742008
I used the fact that if x xor y = z → x xor z = y
I fixed the first element , ran one for loop in vector ‘b’ for doing a[0] xor b[i] and let us say that is c ( c is the constant )
Then another for loop in ‘a’ ( from 1 to n-1) and then did a[j] xor c and found out if there is any number whose xor with a[j] is c to obtain the constant
If it is not there then just exited from the loop and took the next value of b[i]
If it is there then pushed it to vector c ( which is our final answer ) and then took the next value of a[j]
1 Like