*794*

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

One simple way is to scan the complete array for each element of the input elements. That means use two loops. In the outer loop, select elements one by one and count the number of occurrences of the selected element in the inner loop. If an element occurs twice, we can simply print that element.

Here is a sample code for the above method:-

void printRepeatingElements(int arr[], int n) { int i,j; //outer loop for(i=0;i<n;i++) { //inner loop for(j=i+1;j<n;j++) { //if we find repeating element //then print it directly if(arr[i] == arr[j]) printf("%d ",arr[i]); } } }

*Time Complexity:-* O(n^{2})

*Space Complexity:-* O(1)

Click here for Method 2 that involves count array and a better time complexity.

Click here for Method 3 that involves XOR operation and a even better time complexity.