XOR sum of array

Question

When you are given an array of even number of elements:

[$a_1$ $a_2$ $a_3$ ….. $a_n$] ($n$ is even)

Assume the $a_i$ are not all zero

Let $S$ = the XOR sum of all these original elements

You will always be able to remove an element such that the XOR sum of the resulting array is non-zero

If you remove some element $a_i$, the XOR sum of the resulting array is ��S XOR $a_i$”. And there is always an $a_i$ such that “S XOR $a_i$” will never be zero. Why? Can someone help me understand the logic behind it?

Answer 1

$\newcommand{\xor}[0]{\oplus}$

XOR is commutative, associative and self-inverse. We further have that $a\xor b=0 \Leftrightarrow a=b$ (by comparing them bit for bit).

That means

$$ a_1\xor ...\xor a_n \\ = a_1\xor ...\xor a_{i-1}\xor a_{i+1} \xor ...\xor a_n\xor a_i \\ = a_1\xor ...\xor a_{i-1}\xor a_{i+1} \xor ...\xor a_n\xor a_i \\ =( a_1\xor ...\xor a_{i-1}\xor a_{i+1} \xor ...\xor a_n)\xor a_i $$

Now if we add $a_i$, we get $$ ( a_1\xor ...\xor a_{i-1}\xor a_{i+1} \xor ...\xor a_n)\xor a_i \xor a_i \\= ( a_1\xor ...\xor a_{i-1}\xor a_{i+1} \xor ...\xor a_n) $$

because $x\xor a_i\xor a_i = x$ for all $x$ because XOR is self-inverse.

Now assume $a_1\xor ...\xor a_n=c$. Then if $a_n\neq c$, we have again because XOR is self-inverse that

$$ a_1\xor ...\xor a_n=c \\\Leftrightarrow\\ a_1\xor ...\xor a_n\xor a_n=c\xor a_n \\\Leftrightarrow\\ a_1\xor ...\xor a_{n-1} \neq 0 $$

Inversely that means that for example for $c\xor c\xor c$ we have $c\xor c\xor c=c$, and no matter which we remove, we end up with $c\xor c=0$.

But since it was given that $n$ is even, if we had $a_1=...=a_n=c$, then $a_1\xor...\xor a_n=0$, which would be a contradiction to the requirement that at least one of the $a_i$ isn't 0.

Answer 2

As Zoe Allen says, the statement is false if all the $a_i$ are $0$. We assume the problem says not all of the $a_i$ are $0$. You are correct that removing $a_i$ from the sum gives the same result as $S XOR a_i$. If two of the $a's$ are different, removing each of them gives a different result, so removing one of them gives a nonzero result. If they are all the same but nonzero, $S=0$ and removing one of them gives a result that is the same as the one you removed, which we said was nonzero.