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

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

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)