@Priyanka : using my logic,
2,-3,5,4,1,3...
2,-3,-5,4,1,3..
2,-3,-5,4,-1,3..
-2,-3,-5,4,-1,3..
now -3 implies 3 is the answer
to be honest, i hate to ask or be asked such question in interviews :)
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Jul 8, 2010 at 9:53 PM, Priyanka Chatterjee <dona.1...@gmail.com>wrote:
> @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
>> <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.
>>>
>>
>> --
>> 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,
> 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.
>
--
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.
