finding missing element in a set consisting of element from 1 to n, with n-1 elements

Question

The problem is to find the missing number in a set of elements, which is of size n and has elements from 1 to n-1. For e.g in S = {5, 1, 2, 6, 7, 3}, the missing element is 4.

Now I understand that if we perform XOR operation on elements of set and then XOR the result of previous operation with number from 1 to n in the following manner we get the missing number :

5 ^ 1 ^ 2 ^ 6 ^ 7 ^ 3 = 4 = X

1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0 = Y 

now on doing X ^ Y we get the result 4.

I am unable to understand how is this happening. Please help !!

Answer 1

The XOR operation, which we'll denote $\oplus$, has three important properties:

• It is associative: $a \oplus (b \oplus c) = (a \oplus b) \oplus c$.
• It is commutative: $a \oplus b = b \oplus a$.
• For any $a$, we have $a \oplus a = 0$.

That means that, in your case,

$$ (5 \oplus 1 \oplus 2 \oplus 6 \oplus 7 \oplus 3) \oplus (1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 \oplus 7) \\ = (1\oplus1) \oplus (2\oplus2) \oplus (3\oplus 3) \oplus (\color{red}{4}) \oplus (5\oplus5) \oplus (6\oplus6) \oplus (7\oplus7) = 4. $$

Answer 2

Hint (using ^ for XOR): the operator is commutative, associative, and a ^ 0 = a, a ^ a = 0 so:

5 ^ 1 ^ 2 ^ 6 ^ 7 ^ 3 = X

1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = Y 

implies Y = X ^ 4 therefore:

X ^ Y = X ^ (X ^ 4) = (X ^ X) ^ 4 = 0 ^ 4 = 4