**Objective**: Given an array of integers which has all the repeating numbers (twice) but two numbers which are non-repeating. Write an algorithm to find out those two numbers.

**Example**

int [] arrA = {4,5,4,5,3,2,9,3,9,8}; Output: 2 and 8

**Approaches**:

This problem is similar to problem “Find two repeating elements in an array”. There could be multiple solutions like sort the array {O(nlogn)} or use hash map{Time complexity: O(n) , space complexity: O(n)}

In this article we will discuss solution which has time complexity: O(n) and space complexity: O(1), constant extra space.

**Use XOR: time complexity: O(n) and space complexity: O(1)**

- Let’s say non-repeating elements are X, Y.
- A XOR A = 0
- XOR all the elements of array. This will cancel all the repeated elements.
- Result will be X XOR Y, since only X and Y are not repeating.
- 1 XOR 1 = 0 and 1 XOR 0 = 1 with this logic in the result of
*X*XOR*Y*if any kth bit is set to 1 implies either kth bit is 1 either in X or in Y not in both. - Use the above step to divide all the elements in array into 2 groups, one group which has the elements for which the kth bit is set to 1 and second group which has the elements for which the kth bit is 0.
- Let’s have that kth bit as right most set bit (Read how to find right most set bit)
- Now we can claim that these two groups are responsible to produce X and Y.
- Group –1: XOR all the elements whose kth bit is 1 will produce either X or Y.
- Group –2: XOR all the elements whose kth bit is 0 will produce either X or Y.
- See the image below

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class TwoNonRepeatingXOR { | |

public void find(int [] arrA){ | |

//xor will the xor of two non repeating elements | |

//we know that in a XOR b, any particular bit is set if that bit is set in either a or b | |

//we can use this to divide the array elements into two groups where each group will be responsible | |

// to get a and b | |

int xor = arrA[0]; | |

for (int i = 1; i <arrA.length ; i++) { | |

xor ^= arrA[i]; | |

} | |

//get the right most set bit | |

int right_most_set_bit = xor & ~ (xor –1); | |

//divide the array elements into 2 groups | |

int a=0,b=0; | |

for (int i = 0; i <arrA.length ; i++) { | |

int x = arrA[i]; | |

if((x & right_most_set_bit)!=0) | |

a ^= x; | |

else | |

b ^= x; | |

} | |

System.out.println("Non Repeating Elements are: " + a + " and " + b); | |

} | |

public static void main(String[] args) { | |

TwoNonRepeatingXOR t = new TwoNonRepeatingXOR(); | |

int [] arrA = {4,5,4,5,3,2,9,3,9,8}; | |

t.find(arrA); | |

} | |

} |

**Output**:

Non Repeating Elements are: 2 and 8