**Solution**

**Single Number III** https://leetcode.com/problems/single-number-iii/

**Algorithm**

- Important nugget: Since we can easily get the rightmost set bit, let us use it:

set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010

http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/

All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.

Let us see an example.

arr[] = {2, 4, 7, 9, 2, 4}

- Get the XOR of all the elements.

xor = 2^4^7^9^2^4 = 14 (1110) - Get a number which has only one set bit of the xor.

Since we can easily get the rightmost set bit, let us use it.

set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010

Now set_bit_no will have only set as rightmost set bit of xor. - Now divide the elements in two sets and do xor of

elements in each set, and we get the non-repeating

elements 7 and 9. Please see implementation for this

step.

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
xor = 0
for x in nums:
xor = xor ^ x
mask = xor & ~(xor-1)
x,y = 0,0
for n in nums:
if n & mask:
x = x ^ n
else:
y = y ^ n
return [x,y]
```