Print 2 repeating elements in a given array. (Method 3)

Question: Given an array with n+2 elements, all elements of the array are in range 1 to n and also all elements occur only once except 2 numbers which occur twice. Find those 2 repeating numbers.

Input: arr[] = {6, 2, 6, 5, 2, 3, 1}
Output: 6 2

We discussed a method to perform this task using an extra array to count the occurrences of elements, but this approach took an extra space of the range of elements of array. If we have a very wide range, then we will be wasting a lot of space. We can find the two repeating elements using same basic bit operation fundamentals and the XOR operator.

Let the repeating numbers be X and Y, if we XOR all the elements in the array and also all the integers from 1 t0 n, then the final result will be X XOR Y. This is because “A XOR A = 0(zero)”. Now as per bit operations, the 1’s in the binary representation of X XOR Y is corresponding to the different bits between X and Y.

Example:-
8 can be written in binary as 1000.
11 can be written as 1011.
Thus when we do 8 XOR 11 we will get = 0011.

So:- The 1’s occur at 3rd and 4th place, means that of the 2 numbers 8 and 11, the 3rd and 4th bit are different as we can see.

Therefore if the k^th bit of X XOR Y is 1, we can XOR all the elements on the array and also all the integers from 1 to n, whose k^th bits are 1. The result will be one of X or Y. Here is an implementation of the above method.

void printRepeatingElements(int arr[], int size)
{
	int XOR = 0;
	int i, right_most_set_bit_no, x=0, y=0;
	
	//assuming that the integers are in the given range {1,2....n}
	int n = size-2;
	
	for(i=1;i<=n;i++)
	{
		// XOR of all the integers from 1 to n
		XOR = XOR ^ i;
	}
	
	for(i=0;i<size;i++)
	{
		// XOR of all the array elements
		XOR = XOR ^ arr[i];
	}
	
	// Now the variable XOR contains the XOR of 2 repeated numbers
	
	//Get the rightmost set bit in the variable
	right_most_set_bit_no = XOR & ~(XOR-1);
	
	/* Now divide elements in two sets by comparing right most set bit */
	for(i=0;i<size;i++)
	{
		if(arr[i] & right_most_set_bit_no)
			X = X ^ arr[i];	// XOR of first set bit in array
		else
			Y = Y ^ arr[i]; // XOR of second set bit in array
	}
	
	for(i=1;i<=n;i++)
	{
		if(i & right_most_set_bit_no)
			X = X ^ i;	// XOR of first set bit in arr[] and {1,2....n}
		else
			Y = Y ^ i;	// XOR of second set bit in arr[] and {1,2....n}
	}
	
	printf("%d %d",X,Y);
}

Time Complexity:- O(n)
Space Complexity:- O(1)