diff options
Diffstat (limited to 'set_mismatch.py')
-rw-r--r-- | set_mismatch.py | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/set_mismatch.py b/set_mismatch.py new file mode 100644 index 0000000..4c6899b --- /dev/null +++ b/set_mismatch.py @@ -0,0 +1,40 @@ +# 645. Set Mismatch + +""" +you have a set of integers 's' which originally contains all the numbers from +1 to 'n'. unfortunately, due to some error, one of the numbers in 's' was +duplicated to another number in the sett, which results in reptition of one +number and loss of another number. given an integer array 'nums' representing +the data state of this set after the error. find the number that occurs twice +and the number that is missing and return them in the form of an array +""" + + +class Solution(object): + def findErrorNums(self, nums): + """ + :type nums: List[int] + :rtype: List[int] + + 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 the sum of all + numbers and sum of squares of all numbers and given this information we can + get our answer using pure math. facts: + 1. 1 + 2 + ... + n = n * (n + 1) // 2 + 2. 1^2 + 2^2 + ... + n^2 = n * (n + 1) * (2 * n + 1) // 6 + 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: 'a = y - x' and 'b = y * y - x * x' + """ + 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 __name__ == "__main__": + obj = Solution() + print(obj.findErrorNums([1, 2, 2, 4])) + print(obj.findErrorNums([1, 1])) |