An array of size n+1 has integers only from 1 to n. The integers 1 to n can be present 0 or more times in the array. Find the first repeating element in the array. Restrictions: O(n) algo required. Cannot use extra space(not even O(1)) but how you will do if we have to find the all repeating number in given constraints?

Question Seems to bit easy in 1st look but 1st typical Google interview question from their predefined set .in 1st try you won't be able to solve it , i am sure no one can cover the all the test cases in 1st attempt but after trying different test cases we can solve it easily :)

Data Structure Used: Array

Algorithm:(Simple & Straight Forward )

traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Working Code

#include
#include

void printRepeating(int arr[], int size)
{
int i;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++) { if(arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
printf(" %d ", abs(arr[i]));
}
}

int main()
{
int arr[] = {1, 2, 3, 1, 3, 0, 6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}


Its Not Perfect we Need to care of when 0 or any other element occurs more then 2 ?? what happens when it comes multiple times ?? What Happens when array may contains -ive elements ??

suppose you have this array 1 0 2 0 3 0 1 6 4 3 then above algo fail so we need to cover all these case as well isn't it ?? check test case here http://ideone.com/wdxRJ for negative number i will check in last!!!!!!!!

Modified Algorithm(Optimized As Well)
1.While Looping Down from Array Calculate the index of each array element ist clear as all elements will in range of 1 to n so no over flow or underflow conditions.? so index=a[i]%size;
2. then check if value at this index is zero or not if its zero then set its as INT_MIN or -size as you wants. a[index]=-size
3.if above condition fails then check if value at given index is in given range or
not if its in range then multiply the value at given index with -1.
4. if number is less then zero this means its already occurs so print it , multiply with -1 to reset & set value to this index to a[index]=value+size due to time complexity constraints & problem statement i used this when if a number occur say k times algorithm wont fail.
5.

#include
#include
void printRepeating(int arr[], int size)
{
int i,index=0;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++) { index=abs(arr[i])%size; if(arr[index] == 0) arr[index]=-size; else if(arr[index]>0 && arr[index] arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;// try to dry run for each number you will get it !!! :)
}
}
//restore previous array
for(i=0;i arr[i]=abs(arr[i])%size;
}

int main()
{
int arr[] = {2,2,1,1,1,2,2,3,0,0,0,1,1,2,0,7,5};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/i7n7V

further Thoughts: How we will solve if number is between -n to n e.g. total 2n+1 time in unsorted array .Yes As I have already explained the algorithm above will also work here , above we range from 0 to n & here we have -n to n but logic will remain the same why ?? because range is known to us ..i Will suggest to my read to to try out this & do notify it it will fail

Feel Free to Comment :)