Set Mismatch



@vinod23 sorting approach takes at least O(n log n) to sort the array, how did you come up with O(n) ?


Suggest to add a solution as this one, very easy to implement and only 2 pass O(n) iteration.
https://discuss.leetcode.com/topic/97091/c6linessolutionwithexplanation

I used another approach to find the missing number:
It's very easy to find out the duplicate with Approach #4.
Consider the sum of all numbers and the sum of 1 to n, they only differ by (duplicatemissing)
Since we have the duplicate, it's easy to find the missing number as well.Using this method I can exit the 1st loop once I found the duplicate.

Can this be solved using Floyd's Cycle Detection?? I say this because this problem resembles to problem 287. Find the Duplicate Number (https://leetcode.com/problems/findtheduplicatenumber/description/).


@vinod23 Hi, may I ask you a question? What tools you used to draw the above beautiful pictures?

The XOR solution is not clear and scans the array 5 times. Check this XOR solution from the discussion instead https://leetcode.com/problems/setmismatch/discuss/105513

@sstcurry
Approach #7 is the actual XOR solution that works using constant space.Solutions described there https://leetcode.com/problems/setmismatch/discuss/105513 are the complicated ones, which do not require XOR per se:
 Uses additional array. If you allocate additional array you can just solve the problem without using XOR.
 This one uses constant space, mutates the input array (sign inversion) and is identical to sign inversion described in Approach #6. By inverting the sign of numbers you can find both duplicate and missing numbers. Use of XOR is unnecessary in this approach.