https://leetcode.com/problems/set-mismatch

We are given that we have numbers from 1 to n and some number x is here twice and another number y is missing. Let us calculate sum of all numbers and sum of squares of all numbes and given this information we can get our answer, using math! For this we need to use couple of facts:

  1. 1 + 2 + ... + n = n*(n+1)//2. But even if you do not know this formula you can get it in O(n) time and O(1) space.
  2. 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)//6. Again if you do not know this formula, you can get it in O(n) time and O(1) space.

Now, let us consider number A = -sum(nums) + n*(n+1)//2. It is equal to y - x, because each element not equal to x and y will be canceled out. In similar way if we define B = -sum(i*i for i in nums) + n*(n+1)*(2*n+1)//6, it will be equal to y*y - x*x. So, we have system of equations now:

A = y - x B = y*y - x*x.

Dividing one by another we have B/A = y + x, so x = (B/A - A)/2 and y = (B/A + A)/2, which we just return.

Complexity: time complexity is O(n), space complexity is only O(1).

class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        A = -sum(nums) + n*(n+1)//2
        B = -sum(i*i for i in nums) + n*(n+1)*(2*n+1)//6
        return [(B-A*A)//2//A, (B+A*A)//2//A]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0645