Search for 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 a specific order. There is no guarantee on the range of these integers or the number of items 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 value 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 better time complexity than O (n log n) that doesn't choke on small datasets?

Answer 1

In fact, you can apply the idea from the specified topic. But since you have two changes, you have to measure two things.

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

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

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

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