aboutsummaryrefslogtreecommitdiff
path: root/single_number3.py
blob: 2bd4ed2e2cce74485f9a0fb8d5ab0d50594badc8 (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
# 260. Single Number III

"""
given an integer array 'nums' in which exactly two elements appear only once
and all the otherelements appear exactly twice. find the two elements that
appear only once. you can return the answer in any order. you must write an
algorithm that runs linear runtime complexity and uses only constant extra
space.
"""


class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        s = reduce(xor, nums)
        nz = s & (s - 1) ^ s
        n1 = reduce(xor, filter(lambda n: n & nz, nums))
        return (n1, s ^ n1)


if __name__ == "__main__":
    obj = Solution()
    print(obj.singleNumber([1, 2, 1, 3, 2, 5]))
    print(obj.singleNumber([-1, 0]))
    print(obj.singleNumber([0, 1]))