Print 2 repeating elements in an array. (Method 2)

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 the method to find the 2 repeating element using 2 loops, but that method had a great time complexity and it was not at all an optimal solution. We can optimize it using a count array.

This solution is like using a hash table. For simplicity we can use array for storing the counts. Traverse the array once and keep track of count of all the elements in a second count array of size n. When we see an element whose count is already set, print it as a duplicate. Here is an implementation of the same.

void printRepeatingElements(int arr, int n)
{
	//make a count array of size n
	//and initialize all elements to 0
	int *count = (int *)malloc(sizeof(int)*n);

	int i;

	//iterate through the array and increase the count in count array
	for(i=0;i<n;i++)
	{
		//increase the count
		count[arr[i]]++;

		//if any element occurs twice, print it.
		if(count[arr[i]] == 2)
			printf("%d ",arr[i]);
	}
}

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

Click here for an even optimized approach with less space complexity.