What was I thinking! It has the same problem as before. *grrrr*.
AFA I can see this can't be done in log N. Even if we split the problem
space into two we would still have to inspect each to its guts.
On Wed, Sep 2, 2009 at 7:32 PM, ankur aggarwal <ankur.mast....@gmail.com>wrote:
> @rama
> then this ques cannot be solved in log n
> as
> i made only 1 change in the whole array of sorted millions number
>
> 1,2,3,4,5,6,...............,10000,10010,1001,110001.......................
>
> how will u do that ..
>
>
> On Wed, Sep 2, 2009 at 11:50 PM, Ramaswamy R <ramaswam...@gmail.com>wrote:
>
>>
>>
>> On Tue, Sep 1, 2009 at 5:58 AM, ankur aggarwal
>> <ankur.mast....@gmail.com>wrote:
>>
>>> it is a jus a try
>>>
>>> i=1,j=2;
>>> while (a[i]<a[j])
>>> {
>>> j=i;
>>> i=i*2;
>>> }
>>>
>>> now we have i and j and we know that in between these indexes we have a
>>> point z (n as u say) where
>>>
>>
>> Not necessarily. The problem only states that the 1st n elements are
>> sorted. Not that the the 1st n elements are the least of those in the array.
>>
>> So if every element at even location is greater than the previous, then
>> the n need not fall withing [i, j].
>>
>>
>>>
>>> a[z-1]<a[z]
>>> and a[z]>[z+1]
>>>
>>> now apply the abive procedure between i and j
>>>
>>> (its like binary search)
>>>
>>> eg we have m=50 and let n=24 (we dont know this value)
>>>
>>> then for i=16 and j=32 this condition will break ..
>>> now apply this logic in between 16 and 32.
>>> if u find z(or say n) then we can find x easily..
>>> i think i made my logic clear..
>>>
>>> comment plz .
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Yesterday is History.
>> Tomorrow is a Mystery.
>> Today is a Gift! That is why it is called the Present :).
>>
>> http://sites.google.com/site/ramaswamyr
>>
>>
>>
>
> >
>
--
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).
http://sites.google.com/site/ramaswamyr
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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
-~----------~----~----~----~------~----~------~--~---
