suppose k is the sum to be found. @vaibhav: yes it will stop when crossing is there means (j must be greater than i).initially sum = a[i] + a[j] (where i = 0 n j = n- 1) n we will increase i when sum is less than k and decrease j when sum < k.stop if sum == k. and if no i , j found till j > i. then pairs not possible,
On Mon, Jun 27, 2011 at 8:28 AM, Bharath Soma <[email protected]>wrote: > @ankit, sorry i was mistaken its O(nlogn) for searching the two elements... > > > On Mon, Jun 27, 2011 at 8:04 PM, Swathi <[email protected]> wrote: > >> Dave, >> >> Can you provide the psuedo code for this.. >> >> Thanks, >> Swathi >> >> >> On Mon, Jun 27, 2011 at 7:30 PM, Dave <[email protected]> wrote: >> >>> @Sunny. Mea culpa. You are correct. Revised (and correct) algorithm. >>> Do two inorder traversals, one in the usual (descend to the left >>> before descendung to the right) direction and the other in the >>> reversed(descend to the right before descending to the left) >>> direction. Let u and r be the current nodee of the two traversals, >>> respectively. If u + r < x, then advance the usual traversal and >>> repeat the comparison. If u + r > x, advance the reverse traversal and >>> repeat the comparison. If u + r = x, and if u != r, then terminate >>> with success. If u = r, then terminate with failure. >>> >>> Dave >>> >>> On Jun 27, 7:53 am, sunny agrawal <[email protected]> wrote: >>> > @Dave >>> > i think your solution won't work >>> > consider inorder traversal of a BST is 1 6 7 8 15 and x = 14 >>> > initially both u,v (1,1) >>> > according to u your algorithm will proceed like >>> > (1,1) -> (1,6) -> (1,7) -> (1,8) -> (1,15) -> (6,15) ............ -> >>> (15,15) >>> > >>> > and clearly in second step of your solution if (u+v) > x after >>> advancing u >>> > still u+v will be greater than x >>> > so something is wrong >>> > I think your solution will work in case we need to find 2 nodes with >>> > difference x. >>> > >>> > correct me if i am wrong.!! >>> > >>> > >>> > >>> > >>> > >>> > On Mon, Jun 27, 2011 at 6:13 PM, Dave <[email protected]> wrote: >>> > > @Nishant: No need to store the data in an array. Do two inorder >>> > > traversals simultaneously. Let u and v be the current nodes of the >>> two >>> > > traversals, respectively. If u + v < x, then advance the "v" >>> > > traversal. If u + v > x, advance the "u" traversal. >>> > >>> > > Dave >>> > >>> > > On Jun 27, 3:40 am, Nishant Mittal <[email protected]> >>> wrote: >>> > > > do inorder traversal of tree and store values in an array. >>> > > > Now find pairs by applying binary search on array.. >>> > >>> > > > On 6/27/11, manish kapur <[email protected]> wrote: >>> > >>> > > > > -- >>> > > > > You received this message because you are subscribed to the >>> Google >>> > > Groups >>> > > > > "Algorithm Geeks" group. >>> > > > > To post to this group, send email to [email protected]. >>> > > > > To unsubscribe from this group, send email to >>> > > > > [email protected]. >>> > > > > For more options, visit this group at >>> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text >>> - >>> > >>> > > > - Show quoted text - >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to [email protected]. >>> > > To unsubscribe from this group, send email to >>> > > [email protected]. >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > -- >>> > Sunny Aggrawal >>> > B-Tech IV year,CSI >>> > Indian Institute Of Technology,Roorkee- Hide quoted text - >>> > >>> > - Show quoted text - >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > ...Thanks > Bharath > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
