CODEWITHSUNDEEP
pythonbitwise-xor
jung hyemin
jung hyemin

Reputation: 675

XOR to find the missing element between two lists

I try to solve this problem

"Consider an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array."

And one of the solution is below code using XOR

def find(arr1, arr2): 
    result=0 

    # Perform an XOR between the numbers in the arrays
    for num in arr1+arr2: 
        result^=num 
        print result

    return result 


arr1 = [1,2,3,4,5,6,7]

arr2 = [3,7,2,1,4,6]

The result of the function is 5.

I know the basic principle of XOR. But I can't understand how the above code can find the result.

Upvotes: 3

Views: 1866

Answers (2)

Floris
Floris

Reputation: 46435

You start with the result = 0

Then you keep XORing the result with all the elements of each array. The XOR flips all the nonzero bits of the number you currently have.

So when you encounter the same number twice, you have flipped the same set of bits twice - meaning that you are back at the state you started with.

Every number that appears in both lists ends up "canceling itself". The only number that is not canceled is the one that is missing from the second list.

It doesn't matter what each integer is - the bits will flip twice if the number appears twice, and once if the number appears once. It doesn't even matter if the number is missing in the first or the second array.

Upvotes: 0

cs95
cs95

Reputation: 402922

Some important concepts:

  1. XOR of a number with itself is always 0

  2. XOR of a number with 0 is always the number itself

  3. The order of an XOR operation is inconsequential

With this, consider:

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

→ (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ (5) ^ (6 ^ 6) ^ (7 ^ 7)

→  0   ^     0   ^     0   ^      0   ^  5  ^     0   ^   0

→  5

And so, the odd one out remains.

Upvotes: 8

Related Questions