*765*

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.