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

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

by nikoo28
0 comment

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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More