aboutsummaryrefslogtreecommitdiff
path: root/set_mismatch.py
diff options
context:
space:
mode:
Diffstat (limited to 'set_mismatch.py')
-rw-r--r--set_mismatch.py40
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]))