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.
Returns the duplicate value in array t[n], which contains numbers 1 to n-1
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];
}
}
}
yogeshwar 0 Newbie Poster
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
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.