CODEWITHSUNDEEP
pythonlogical-operators
Dee
Dee

Reputation: 47

Why does the XOR return the missing value in these two lists?

I was watching a video on youtube regarding a coding interview and one of the questions was to find the missing value between two lists. This is one of the approaches he took but I dont understand how exactly 'a' ends up being the missing value.

def function(nums,num2):
    a = 0
    for num in nums:
        a ^= num
        print(a)
    for num in num2:
        a ^= num
        print(a,"\n")
    return a

function([1,2,3,4],[3,1,2])

Upvotes: 3

Views: 77

Answers (4)

aadithya venkat
aadithya venkat

Reputation: 28

You would have to dig deep into the basics of how XoR works based on Digital Design of Circuits. So if you give the same input XoR is going to always return 0 if you pair it up with the same input as per the structure of digital design. So as Tom Karzes pointed out the other values get nullified leaving you with the remaining one. There are some other problems too that can be solved with XoR like finding the unique element in an array filled with a copy of each element

This wiki will give you a good description of how the XOR gate works

Upvotes: 0

Devesh Kumar Singh
Devesh Kumar Singh

Reputation: 20500

In the solution above, we are taking the xor of all the elements in the list.

When you take XOR of two elements which are same, you get 0

>>> 1^1
0

Hence when you take XOR of all elements in the list, the elements which are same cancels out, since XOR is commutative and associative, and the element which is not paired remains.

>>> 1^2^3^4^3^1^2
4
>>> 1^1^2^2^3^3^4
4

Upvotes: 0

rdas
rdas

Reputation: 21285

When you XOR an integer with itself, you get 0.

So if you have a list [1,2,3,4] and another list [3,1,2]. Now you XOR everything together, the same elements cancel out - leaving the 1 element which is different.

[1,2,3,4] xor [3,1,2] = [4]

By the way, this assumes that the lists differ by only one element. If not, you'll get the XOR of all the different elements.

Upvotes: 3

Tom Karzes
Tom Karzes

Reputation: 24092

Think of it this way: You're returning (1^2^3^4)^(3^1^2). Well, XOR is commutative and associative, so this is equal to (1^1)^(2^2)^(3^3)^4. But x^x is 0, so this is equal to 4. In other words, pairs of matching values cancel, leaving you with the one unmatched value.

Upvotes: 4

Related Questions