Click here to see the full article post
@dejokz I have added the explanation. Please have a look. Thanks.
@vinod23 sorting approach takes at least O(n log n) to sort the array, how did you come up with O(n) ?
Approach #5 Using Extra Array[Accepted], shouldn't the space complexity be
O(1)? Although the length of
n, but it never grows and I think we can consider it using constant space.
Suggest to add a solution as this one, very easy to implement and only 2 pass O(n) iteration.
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 (duplicate-missing)
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/find-the-duplicate-number/description/).
I did still not understand and how to calculate the missing number. Can some one explain it more clear way?
@mrpandey That's a good idea.
@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/set-mismatch/discuss/105513
Approach #7 is the actual XOR solution that works using constant space.
Solutions described there https://leetcode.com/problems/set-mismatch/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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.