1

I was doing practice on search algorithms for arrays.

I had come across with problem of finding missing and duplicate element by using XOR approach for a given array of elements containing integer from 1 to n. Find the missing and duplicate elements in an array in linear time and constant space I am very well able to understand that how we can get the separate values of X and Y ( one is repeating and another is duplicate )

However I am unable to understand how are we able to decide that which one is repeating and which one duplicate.

( as per given solutions I could see xor result of XOR over list which has set-bit gives missing element and other list gives duplicate ). However I am unable to understand the logic to reach on this decision.

Please help me to understand the logic behind this decision.

JeetToGeek
  • 11
  • 2
  • You can do another scan of the array and see which one of the numbers is the duplicate and which one is missing, doesn't change overall time complexity. – maraca Mar 18 '18 at 13:17

2 Answers2

0

While doing Xor operation, if number present even times Xor will be zero and if it presents an odd number of times then Xor will be that number.

Ex- xor of even freq number 5^5 or 3^3^3^3 will be zero. Ex- xor of odd freq number 5^5^5^5^5=5 or 3^3^3=3 will be the same number.

If look closely you can see that finding a duplicate or missing both are referring to the same thing. Let's take an example and understand- because if some number is missing it means a frequency of that number will be zero which is even number. and if some integer is duplicate, it means a frequency of that number will be two which is even number and whenever you do Xor of the same number even number of times it will lead to zero

Ex- consider an dupArray(A)={1,2,3,5,5},missingArray(B)={1,2,3,4,_} range from 1 to 5 Actual array(C)={1,2,3,4,5}

A^C={5}

B^C={5}

Kanahaiya
  • 406
  • 2
  • 11
-1

if you have found x & y then simply make a loop in existing array again and check if x doesn't exist in the array then the missing number is x otherwise it will be y.

Siddhant
  • 41
  • 5