sorry , there was a typo
'Have two array" read it as "Have two pointers"
-Manish
On May 16, 1:04 pm, Modeling Expert <cs.modelingexp...@gmail.com>
wrote:
> @Divya I think your solution is correct. To do in constant time , we
> can use BST itself instead of storing in array.
> Have two array , make first point to left most , make second point to
> right most member, now start your algorithm while making
> these two pointers move. Left pointer should move in 'inorder' style
> while right pointer should move in 'reverse inorder style'
> if ( *LeftPtr + * RightPtr > k ) Decrement ( RightPtr)
> if ( *LeftPtr + * RightPtr < k ) Increment (LeftPtr)
> else WeHaveAnswer
>
> -Manish
>
> On May 15, 6:49 am, Yalla Sridhar <sridhar2...@gmail.com> wrote:
>
>
>
> > if the tree has parent pointer then we can apply similar approach,,
> > increment and decrenent... and can also be done in O(1)
>
> > have to poninters pointed to the min and max nodes and them move pointers by
> > checking the sums..
>
> > On Fri, May 14, 2010 at 5:03 PM, 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
>
> > >> 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<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
> > athttp://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
> athttp://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.
