Hard

# 243. Find two non-repeating numbers in an array in O(n) time and O(1) space

Objective:  Given an array of integers that has all the repeating numbers (twice) but two numbers that 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 the 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 a solution that has time complexity: O(n) and space complexity: O(1), constant extra space.

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

1. Let’s say non-repeating elements are X, Y.
2. A XOR A = 0
3. XOR all the elements of the array. This will cancel all the repeated elements.
4. The result will be X XOR Y since only X and Y are not repeating.
5. 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.
6. Use the above step to divide all the ele­ments in the array into 2 groups, one group which has the ele­ments for which the kth bit is set to 1 and a sec­ond group which has the ele­ments for which the kth bit is 0.
7. Let’s have that kth bit as the rightmost set bit (Read how to find right most set bit)
8. Now we can claim that these two groups are respon­si­ble for pro­duce X and Y.
9. Group –1: XOR all the ele­ments whose kth bit is 1 will pro­duce either X or Y.
10. Group –2: XOR all the ele­ments whose kth bit is 0 will pro­duce either X or Y.
11. See the image below

Output:

`Non Repeating Elements are: 2 and 8`