CODEWITHSUNDEEP
arraysalgorithmxor
Manvendra Singh
Manvendra Singh

Reputation: 626

Find repeating and missing numbers in a given array

For a given array A containing numbers from 1 to N, I want to find the pair of numbers (x,y) which is repeated and missing. Example A = [1, 3, 3] then x = 3 and y = 2.

While I know that this problem can be solved by taking the xor approach mentioned here https://stackoverflow.com/a/5767648/5031518. I am failing to understand the last part of the solution where the values of x and y are extracted from x ^ y by splitting the array based on a set bit.

It would be helpful if someone can explain me why the xor of two list results in the value of x and y respectively.

Upvotes: 1

Views: 315

Answers (1)

MBo
MBo

Reputation: 80275

At the first stage you calculate xor of values in full range 1..N and in your list

1  2  3 .. x .. N  
1  2  3 ..   .. N  y

xor of all paired items gives 0, so result is p = x xor y

Value p is non-zero, but what bits are set? Those different in x and y.

So we can find any 1-bit from p, call it mask, and perform the same procedure on values 1..N and your list, choosing only values that have this bit set

for all v in 1..N and in list:   
   if ((v & mask) == mask):
       newxor ^= v

After all, newxor contains or x or y (all other items participating here are paired), and we can find another item with

 xy = p ^ newxor

Note: we cannont distinguish what item was repeated, and what was missed, just get pair of them.

For your example 

p = 1^2^3^1^3^3 = 1 = 001 binary

repeating procedure with mask 001b engages only odd numbers

 newxor = (1 xor 3) xor (1 xor 3 xor 3) = 3

and the rest number is

 3 xor 1 = 2

For example (1,2,2) we get the same p

p = 1^2^3^1^2^2 = 1 = 001 binary

and the same newxor = 3 and the same rest value xy=2

Upvotes: 1

Related Questions