Distinguishing extra element from two arrays?

Question

One of my friend was asked this question in an interview - - You have given two integer arrays each of size 10. - Both contains 9 equal elements (say 1 to 9) - Only one element is different. How will you find the different element? What are different approaches you can take? > One simple but lengthy approach would be - sort both arrays,go on comparing each element,on false comparison, you'll get your result. So what are different approaches for this? Specify logic as its expected in an interview. Not expecting a particular code in a specific language. Pseudo code will suffice. (Please submit one approach per answer) > My purpose of asking this question is, its OK when array sizes are small.But when array size increases, you must think of a very efficient n faster way.Its never desirable to use comparisons in such case.

Answer 1

Let's call the arrays A and B and let their unique elements be a and b, respectively.

First, take the sums of both arrays and subtract one from the other; since everything else cancels,

sum(A) - sum(B) = a - b = s.

Then, multiply the elements of both arrays and divide one by the other. Again, things cancel, so

mult(A) / mult(B) = a / b = r.

Now, from these, we get:

a = rb, so rb - b = s or b = s / (r - 1) and then a = rs / (r - 1)