@Ashish :Firstly your code will never run in O(k) time and also fails to
provide correct answer.
In your code the index of first negative encountered is
returned
test for this sample: k=5 , A=2,3,5,4,1,3..... your code returns 2
while answer is 3.
> alternate way is to check for a ring
> //***************
> int count =0; int i =0;
> while (count ++ < n){
> if (i==a[i]) {i++;continue;}
> if (a[i] <0) return i;
> i=a[i];
> a[i] *=-1;
> }
> return -1;
> //******************
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Thu, Jul 8, 2010 at 1:32 PM, Priyanka Chatterjee
> <[email protected]>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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
