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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.