Start New Discussion within our Software Development Community

Returns the duplicate value in array t[n], which contains numbers 1 to n-1.

Given two approaches with O(n) and O(n-square) complexities.

O(n)
===
int dupinarray(int a[],int n)
{
int total=0,i;
for(i=0;i<n;i++)
total+=a[i];
return (n-((n*(n+1)/2)-total));
}

O(n-square)
========
int dupinarray(int a[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j])
return a[i];
}
}
}

dear friend
this code doesnot work if suppose 6&4 are missing and two 5s are present
then this code would say the array doesnot contain duplicate element
....

so the code will not work

instead u can try this logic:

scan the array sequentially and on finding a number say n store it in a variable and replace the no by -n
then traverse to the n th cell and repeat the process..
If u reach a cell which contains negative element, the array contains a duplicate element

Note there is a special condition to check .. if the no is present in its own cell say n is present in nth cell, then check the next cell...(if the next cell is already negative , again move to the next cell)


i hope u understand whats wrong


later u can make all no as positive to retain the values