0

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];
}
}
}
2
Contributors
1
Reply
2
Views
11 Years
Discussion Span
Last Post by yogeshwar
0

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

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.