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
}