@Ashish: i could not get the answer -3 as well . It is indeed a tough
question. :)
On 9 July 2010 10:31, Ashish Goel <ashg...@gmail.com> wrote:
> @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<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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
