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>
> .
> 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.
