CODEWITHSUNDEEP
pythonarraysseriesxor
Avi
Avi

Reputation: 2283

Finding the missing number in array in Python using XOR

The following code work well and finds the missing number of contiguous array using XOR. I would like to ask why the first loop starts at 1 and ends at n and the second starts at 2 and ends at n+2?

a = [1, 2, 3,4, 5, 6,8] 
n = len(a)
x1 = a[0]
x2 = 1
for i in range(1, n):
 ##   print (i)
#print (' ')
for i in range(1, n): 
        x1 = x1 ^ a[i]
        print (a[i],x1)
print (' ')
for i in range(2, n + 2): 
        x2 = x2 ^ i 
    ##    print (i,x2)
##print (' ')
print (x1 ^ x2 )

Upvotes: 1

Views: 364

Answers (1)

Adam.Er8
Adam.Er8

Reputation: 13413

the fact that the ranges don't start at 0 is due to the fact you initialize x1 and x2 to the first value of the array.

you can start at 0 just as easily, with x1, x2 = 0, like this:

a = [1, 2, 3, 4, 5, 6, 8]
n = len(a)
x1 = 0
x2 = 0
for i in range(0, n):
    x1 = x1 ^ a[i]
for i in range(0, n + 2):
    x2 = x2 ^ i
print(x1 ^ x2) # still prints 7

the fact you go all the way to n+2 (which is actually just up to n+1 because the end is not inclusive) is because the array has a missing element, so in your case n+1 is 8, and without XORing it to x2 you'd end up with the wrong value (in this case, 15, which is 7^8).

to clarify: you have to XOR the actual values, with the expected values, to find the missing one.

the first range goes on all actual values, while the second one goes on all possible values, which is up to n+1.

Upvotes: 2

Related Questions