Labels

Wednesday, June 29, 2011

* Find duplicates in O(n) time and O(1) extra space

/*Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.*/

#include "stdio.h"

#include"stdlib.h"
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]<size)
arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;
}
}
//restore previous array
for(i=0;i <size;i++)
arr[i]=abs(arr[i])%size;
}

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

No comments:

Post a Comment