Hi,
My solution is :
int Find_repeat(int *array, int n)
{
int index=0, index1 =0;
while(array[index]>0) // assume number are in between 1 to n and size of
array is n also atleast one is repeated.
{
array[index] = -array[index];
indeax = abs(array[index])-1;
}
printf("repeated number is = %d", index+1); //if you want to print
otherwise comment out
while(array[index1]<0)
{
array[index1] = -array[index1];
index1 = abs(array[index1])-1;
}
return index+1;
}
*Time complexity O(n);
space complexity O(1);*
On Fri, Jul 9, 2010 at 9:18 AM, aejeet <aej...@gmail.com> wrote:
> Hi Umesh/Priyanka,
> Ur solution felt so intuitive once i understood it.
>
> Cheers
>
>
>
> On Jul 8, 11:21 am, umesh kewat <umesh1...@gmail.com> wrote:
> > Hi Priyanka,
> >
> > Thanks For explaining my solution with example..
> >
> > --
> > Thanks & Regards
> > Umesh Kewat
> >
> > On Thu, Jul 8, 2010 at 1:32 PM, Priyanka Chatterjee <dona.1...@gmail.com
> >wrote:
> >
> >
> >
> >
> >
> > > I totally agree with Umesh's algo which gives O(K+1) time and an
> inplace
> > > solution. The only point is the first K+1 numbers may get negated and
> the
> > > array is modified. In that case after finding the duplicate we can
> traverse
> > > the array again for the first k+1 no.s and make the negative numbers
> > > positive.
> >
> > > code is -(considering array contains only positive numbers)
> >
> > > for(i=0;i<k+1;i++){
> > > if(A[abs(A[i])])<0) return abs(A[i]); //1st duplicate, abs is absolute
> > > function
> >
> > > A[abs(A[i])]*=(-1);
> >
> > > }
> >
> > > I am explaining Umesh's solution with an example
> >
> > > let k=6 , k<n
> >
> > > A= 1,6,4,5,2,6,3,..........
> > > A[0]-1st element, a[k]-k+1 element in array
> >
> > > now A[0]=1; and A[1]=6 now A[1]= -6
> > > A[1]=6 and A[6]=3 now A[6]=-3
> > > A[2]=4 and A[4]=2 now A[4]=-2
> > > A[3]=5 and A[5]=6 now A[5]=-6
> > > A[4]=-2 and A[abs(-2)]=4 now A[2]=-4
> > > A[5]=-6 and A[abs(-6]<0 therefore return 6
> >
> > > time complexity=O(k+1) and very much inplace solution .
> >
> > > --
> > > Thanks & Regards,
> > > Priyanka Chatterjee
> > > Final Year Undergraduate Student,
> >
> > > Computer Science & Engineering,
> > > National Institute Of Technology,Durgapur
> > > India
> > >http://priyanka-nit.blogspot.com/
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Thanks & Regards
> >
> > Umesh kewat
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Thanks & Regards
Umesh kewat
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
