Finding a missing and duplicate integer from an unsorted list of consecutive integers

Question

This question is very similar to How to find a duplicate element in an array of shuffled consecutive integers?, but has some additional requirements.

You have a list of consecutive integers, in no particular order. There is no guarantee on the range of these integers or the number of elements in the list.

This list is missing one integer and contains a duplicate of another integer.

An example of such a list is {16, 12, 13, 17, 14, 13}; in this case, the missing integer is 15 and the duplicated is 13.

What is the most time-efficient way to find both of these numbers, taking into account both small and large data sets? Is there any solution with a better time complexity than O(n log n) that doesn't choke on small data sets?

Answer 1

Actually you can apply the idea from the referenced topic. But since you have two changes, you should measure two things.

For example, measure sum of values and sum of squares and compare them with expected ones. If number A is duplicated and number B is missing, you will have:

• sum - expected_sum=A-B
• sum_of_squares - expected_sum_of_squares=A^2-B^2

Having (A-B) and (A^2-B^2) you can get (A+B)=(A^2-B^2)/(A-B).

Having (A+B) and (A-B) you can get A=(A+B)/2+(A-B)/2 and B=(A+B)/2-(A-B)/2