Find both the duplicated number and the missing number

How to find the duplicate and missing number in an array of unsorted set of continuous numbers (1 to N)?

Solution from http://anuviswan.blogspot.com/2007/08/missing-and-duplicate-number-algorithm.html:

1. Find RealSum = ( sum of all numbers in array )
2. Find RealProduct = ( product of all numbers in array )
3. Find ExpectedSum = n*(n+1) / 2 where n is number of integers
4. Find ExpectedProduct = n!

Equation 1 : X - Y = (RealSum - ExpectedSum)
Equation 2 : X/Y = (RealProduct / ExpectedProduct)

Solve this equation.

X is the duplicated number
Y is the missing number

这种算法易于理解，且实现很简单，但有overflow的危险。能否用异或的方法解决呢？其实也是可以的。

把这个给定的set里面所有的数都xor一遍，可以看出，duplicate的两个数字必定相互抵消。换句话说，相当于duplicate的数字missing了。

从而我们可以得出结论：如果set里面有duplicate，那么finding duplicate的问题可以等价为finding missing element的问题。如果set里面有一个数字duplicate，那么可以转化为求一个missing number的问题。如果set里面有一个duplicate和一个missing，那么找出它们和找出两个missing numbers是等价的。