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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.