Missing sequence number problem solved with XOR-CodePudding

I'm trying to understand how the XOR operation managed to solve the problem PermMissingElem

I know one of the properties of XOR is that:

A ⊕ B = C
C ⊕ A = B
C ⊕ B = A

>>> 3 ^ 4
7
>>> 7 ^ 3
4

This can be repeated for any number of operations, in this case it was 2 numbers, but it could be 3, 4, 5... n

Another property is that:

A ⊕ A = 0
A ⊕ 0 = A

>>> 3 ^ 3
0
>>> 3 ^ 0
3

But looking at the problem PermMissingElem how was it possible to guarantee that the last operation would be exactly the number that was missing? Is there any literature on this algorithm, has anyone talked about it?

A = [1,2,3,4,5,7,8,9,10,11]

missing_element = len(A) 1

for idx,value in enumerate(A):

    print(missing_element, value, (idx 1), ' = ', missing_element ^ value ^ (idx 1))
    missing_element = missing_element ^ value ^ (idx 1)

out

11 1 1  =  11
11 2 2  =  11
11 3 3  =  11
11 4 4  =  11
11 5 5  =  11
> 11 7 6  =  10
10 8 7  =  5
5  9 8  =  4
4 10 9  =  7
> 7 11 10 =  6

as can be seen:

11 ⊕ 7 ⊕ 6 = 10
7 ⊕ 11 ⊕ 10 = 6

CodePudding user response：

Since you know, there is exactly one of each number in the input in range [1..n 1] except for one missing k and the fact that a ⊕ a = 0,

if you have another array [1..n 1], without missing k,

then, on merging these arrays, we will have one big array with every number repeated twice, except k. So, if we XOR all elements of this array, each repeated element cancels itself and we will be left with k, which is your missing number.

CodePudding user response：

The XOR operation is commutative, the order of application does not matter.

Two XORs with the same value cancel each other.

So, starting from 0 and applying any sequence of XORs, followed by the same sequence that includes an extra element, only the effect of the extra element remains.

E.g. 0 ⊕2⊕3⊕1⊕5 ⊕1⊕2⊕3⊕4⊕5 has the same effect as 0⊕1⊕1⊕2⊕2⊕3⊕3⊕4⊕5⊕5, or 0⊕4.