https://leetcode.com/problems/single-number-iii

I think it is rather hard problem than medium. If you solved Single Number I or II problems you probably can immediately say, that this problem is about bit manipulations. So, the first step is to evaluate XOR of all numbers, but what is next? It is indeed very difficult question, if we are not allowed to use extra memory and we want to stay with O(n) iterations. So, what exactly we get, when we evaluate XOR of all numbers? We will have num1 ^ num2, where num1 and num2 are desired numbers. We need to use all the imformation given in statement, and so these numbers are different, and it means there will be at least one bit, where they differ, it means one number of num1 and num2 have this bit equal to 0 and other to 1 . Let us remember this bit and traverse data once again: making XOR of numbers, where this bit is equal to 1. Then we get exactly one of our desired numbers. Finally, we can find other number, using num2 = s^num1, where s is XOR of all numbers.

  1. Evaluate s - XOR of all numbers.
  2. nz is non-zero bit. s&(s-1) trick is used to remove last 1: for example for number s = 110100, the value s&(s-1) = 110000, and s & (s-1) ^ s = 110000 ^ 110100 = 000100.
  3. We evaluate num1, using only numbers, where this bit is not absent.
  4. Finally, we evaluate num2 = s ^ num and return answer.

Complexity: time complexity is O(n), where we do 2 passes over data. Additional space complexity is O(1), we use just several additional variables.

class Solution:
    def singleNumber(self, nums):
        s = reduce(xor, nums)
        nz = s & (s-1) ^ s
        num1 = reduce(xor, filter(lambda n: n & nz, nums))
        return(num1, s ^ num1)

Update Thanks @rkmd for pointing out nicer ways to use reduce function!

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