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.

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________