aboutsummaryrefslogtreecommitdiff
path: root/set_mismatch.py
blob: 4c6899b9674ca885b9ea26fc90f7899b4a24aae7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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]))