- #1

Taylor_1989

- 402

- 14

- TL;DR Summary
- I am having an issue understanding how the given algorithm, is actually working.

Recently I have been reading up about the logical operations OR, AND and XOR. Whilst reading about XOR I cam across a method using XOR to find the missing number in a given array, but I just can't understand how or really why it works. The algorithm is displayed below.

What I can seem to understand is two things.

1. Why for the second loop has the array length been extend by 2?

2. In effect from what see is that the algorithm is comparing the last elements within each for loop, but I just understand how this gives the missing number? As I understand XOR compare the binary number of the given integer and if both integers are the same will result in 0 or if not the same will result in a new integer i.e 16 ^ 15 = 1. But why compare the array and update x1 and why compare x2 with i and update.

I have runt the print out of each line of the itterartion to see if I could gain some insight to what going on but to be honest confused me more. Could maybe some explain in laymen terms if possible.

Find missing number in array:

```
A = [2, 3, 1, 4, 6, 7]
x1 = A[0]
x2 = 1
for i in range(1, len(A)):
x1 = x1 ^ A[i]
for i in range(2, len(A)+2):
x2 = x2 ^ i
print('--'*10)
print(x1 ^ x2)
```

What I can seem to understand is two things.

1. Why for the second loop has the array length been extend by 2?

2. In effect from what see is that the algorithm is comparing the last elements within each for loop, but I just understand how this gives the missing number? As I understand XOR compare the binary number of the given integer and if both integers are the same will result in 0 or if not the same will result in a new integer i.e 16 ^ 15 = 1. But why compare the array and update x1 and why compare x2 with i and update.

I have runt the print out of each line of the itterartion to see if I could gain some insight to what going on but to be honest confused me more. Could maybe some explain in laymen terms if possible.