How to solve a problem on or?

Question

Algorithms

Given an m-array of integers, the only operation that can be performed is to find out the xor of 2 elements under indices i, j. How to find out where 0 is? (it is guaranteed that 0 is always present).(Please explain if possible).Thanks in advance!
This task: https://codeforces.com/contest/1364/problem/E (well, more precisely, part of it, in order to restore the permutation you need to know where 0 is), but I can’t figure out how to find 0 even when I read the analysis.
Just a clear explanation will also be enough (or where to read to make it clear how to solve).

Answer 1

It's impossible.
Let's say we have an array that is NOT WHOLE zeros and contains at least one zero.
Let's take any non-zero element a and pro-XOR'im with it all elements of the array.
The zero has moved to another location, but the results of our operation a[i] xor a[j] have not changed.
It turns out that the first array is indistinguishable from the second, and the zeros in them are in different places.
For example: array 0 1 2 3 is indistinguishable from array 1 0 3 2.
0 xor 1 = 1 … 1 xor 0 = 1
0 xor 2 = 2 … 1 xor 3 = 2
0 xor 3 = 3 … 1 xor 2 = 3
1 xor 2 = 3 ... 0 xor 3 = 3
1 xor 3 = 2 ... 0 xor 2 = 2
2 xor 3 = 1 ... 3 xor 2 = 1
Well, 0 xor 0, 1 xor 1, 2 xor 2 and 3 xor 3 have always been zeros.
------------------
In the version with OR, we take a[0] or a[i], supporting the AND of these sums and counting how many times this same AND occurs among our sums.
1) If numbers greater than AND occur as many times as [well, count how many numbers from 0 to N−1 will have all these bits] - discard our 0th number, as well as the verified numbers whose sum is NOT the same as AND, and start over.
EXAMPLE: 2 3 4 0 1
2 or 3 = 5, AND=5
2 or 4 = 6, AND=2 - bit 2 will only have 2 and 3 here, discard 2, 3 and 4.
If AND occurs 2 ^k −1 times (k is the number of bits in AND), leave ONLY THESE cases and start again from the beginning.
EXAMPLE: 2 1 0 3
2 OR 1 = 3, AND=3
2 OR 0 = 2, AND=2
2 ^k−1=1, and one meeting of the number 2 is enough for us - we leave 2 and 0.
There are three numbers left - we act according to the standard algorithm.
There is one number left - it is 0.
There are two numbers left - one is 0, the other is a bit. We must find a number that does not have this bit. Again we go through the result of the previous round, summing first with one, then with the other. We see the difference - it is clear where is 0 and where is bit.