### Find duplicates in a array of elements

You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Hint: You are allowed to destroy the array elements.

Hint: You are allowed to destroy the array elements.

#include

ReplyDeletevoid check(int a[],int j);

int main()

{

int a[10]={3,5,1,7,8,2,9,10,9,5};

int i,j;

for(i=0;i<10;i++)

{

if(a[i]>0)

{

j=a[i]-1;

a[i]=0;

check(a,j);

}

}

printf("repeated numbers in the given array are:\n");

for(i=0;i<10;i++)

{

if(a[i]<-1)

{

printf("%d\n",i+1);

}

}

return 0;;

}

void check(int a[],int j)

{

int k;

if(a[j]>0)

{

k=a[j]-1;

a[j]=0;

check(a,k);

a[j]--;

}

else

a[j]--;

}

@pankaj can you please explain the logic.:)

ReplyDeletesince all the numbers in array are b/n 1 to n store the negative of no. of occurrences of an int i in a[i-1]. e.g. since a contains only one 1 so a[0] will be -1 but a contains two 5s so a[4] will be -2 and so on.

ReplyDelete@pankaj you are right

ReplyDeleteBelow method works in O(n) and constant extra memory space.

ReplyDeletetraverse 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

}