hmmm i already realised that and even mailed that before :)
and if we want to use constant space do not make an array. the bst
itself is good enough to do what we are doing.
On 5/14/10, anna thomas <annathoma...@gmail.com> wrote:
> @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum,
> then decrement the 2nd ptr(ptr at end of array)
> In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
> dec ptr2 1+4 = 5 (sum < 6)
> inc ptr2: 2+4 =6 (got the ans)
>
> But the qs mentions that it should be in O(1) space.
> Regards,
> Anna
>
>
>
> On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf
> <rohit.kumar.sa...@gmail.com>wrote:
>
>> @divya : i guess... it wont work.
>> consider Array {1,2,3,4,123456}
>> and you want sum 6.
>>
>> @prashant: Is it O(n)?
>>
>> I guess after converting to array and removing all entries > sum, we
>> should
>> start with the smallest element
>> and scan the elements from last till we get some value x which together
>> with the smallest value sums to < sum. Call this position POS1.
>> If we get required sum somewhere in the process, cool !
>> Else take drop the elements after POS1 and also the smallest element.
>> Recurse on the remaining.
>>
>> --------------------------------------------------
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>
>>
>>
>> On Fri, May 14, 2010 at 3:51 PM, Prashant K
>> <prashant.r.k...@gmail.com>wrote:
>>
>>> i think it can done like this,
>>> assume we have to find 'x' and 'y' wer s='x'+'y'
>>>
>>> 1) select ith node from tree (from beginning to end)
>>> 2) y= s - " ith number (node)"
>>> 3) now search for 'y' in BST if we found then there is node such that s=
>>> x
>>> + y; otherwise no..
>>>
>>> -- Prashant Kulkarni
>>> || Lokaha Samastaha Sukhino Bhavanthu ||
>>> || Sarve Jana Sukhino Bhavanthu ||
>>>
>>>
>>>
>>> On Fri, May 14, 2010 at 2:47 AM, divya jain
>>> <sweetdivya....@gmail.com>wrote:
>>>
>>>> form a sorted array from inorder traversal of tree. now take to
>>>> pointers
>>>> one to the beginning of array and other at the end. now check if the sum
>>>> of
>>>> element is greater than reqd sum then increment 1st ptr. if their sum is
>>>> less than reqd sum then decrement 2nd ptr. if their sum is equal to the
>>>> reqd
>>>> sum then this is the ans..
>>>> hope it will work..
>>>>
>>>>
>>>> On 13 May 2010 20:11, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote:
>>>>
>>>>> given a bst... find two nodes whose sum is equal to a number k ... in
>>>>> O(n) time and constant space...
>>>>>
>>>>> --
>>>>> With Regards,
>>>>> Jalaj Jaiswal
>>>>> +919026283397
>>>>> B.TECH IT
>>>>> IIIT ALLAHABAD
>>>>>
>>>>> --
>>>>> 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.
>>>>
>>>
>>> --
>>> 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.
>>
>
> --
> 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.
>
>
--
--------------------------------------------------
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
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.
