4

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?

Community
  • 1
  • 1
Collin Dauphinee
  • 13,664
  • 1
  • 40
  • 71

1 Answers1

8

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

maxim1000
  • 6,297
  • 1
  • 23
  • 19
  • 2
    It seems that it a bit more complicated. In the example above, you expect a sum of 89, but you find only 87. You can conclude that the number that is missing (15) is 2=89-87 units higher than the duplicate number (13). However, this is not sufficient to conclude. – B. Decoster May 04 '11 at 15:45
  • Fezvez: thanks, I incorrectly read the problem. Now all should be OK. – maxim1000 May 04 '11 at 15:59
  • However, with the edited answer, I can only agree! Nice finding! – B. Decoster May 04 '11 at 16:02