**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)**

- Let’s say non-repeating elements are X, Y.
- A XOR A = 0
- XOR all the elements of the array. This will cancel all the repeated elements.
- The 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 the array into 2 groups, one group which has the elements for which the kth bit is set to 1 and a second group which has the elements for which the kth bit is 0.
- Let’s have that kth bit as the rightmost set bit (Read how to find right most set bit)
- Now we can claim that these two groups are responsible for 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:**

**Output:**

Non Repeating Elements are: 2 and 8

if the repetition is odd times, your logic fail then.

try with input {2,3,1,3,2,7,3}

Thanks for pointing it out, will correct the objective of the question