We solve this using segment tree. http://codepad.org/5jVxLmsA
On Sat, Jun 26, 2010 at 1:38 PM, Amit Jaspal <iit2007...@iiita.ac.in> wrote: > Srry i wrote wrongly i will store C[i] if C[i]-K is not found in BST.if > found there is a sub array.. > So now dry run... > C[]=6,-1,7. > K=7. > And Yeah we will have to build a balanced BST for sure.. > > > > On Sun, Jun 27, 2010 at 1:57 AM, Dhritiman Das <dedhriti...@gmail.com>wrote: > >> >> @amit: Need to store indices also in the tree. >> Did you mean a "self-balancing" BST, like AVL or RB-Tree. >> Else worst case is O(n^2) for all positive numbers >> >> >> On Jun 25, 2:55 am, Amir hossein Shahriari >> <amir.hossein.shahri...@gmail.com> wrote: >> > @divya: yes you're right my algo doesn't work for negative values >> > >> > @amit: you're algo is not correct for negative values either since >> > when you find C[j] - C[i] =k >> > there is a constraint that j>i but your BST would not support that e.g. >> : >> > k=7 >> > A[]={6,-7,8} >> > C[]={0,6,-1,7} >> > your result would be true because when you see 6 in C you search for >> > -1 you can find it in your BST but there is no subarray that sum up to >> > 7 >> > >> > i think that in your solution we must keep the indexes with the values >> > of C in BST >> > >> > On 6/23/10, divya jain <sweetdivya....@gmail.com> wrote: >> > >> > > @amir >> > >> > > ur algo works only for positive elements array.. >> > >> > > correct me if m wrong >> > >> > > On 23 June 2010 00:28, Amir hossein Shahriari < >> > > amir.hossein.shahri...@gmail.com> wrote: >> > >> > >> for each element find sum[i] which is the summation of all elements >> with >> > >> index less than or equal to i ( note that this array is always >> sorted) >> > >> this >> > >> can be done in O(n) >> > >> then sum[i]-sum[j] when j<i is the sum of range [j,i] >> > >> then for each sum[i] binary search for sum[i]-k in the array sum >> > >> which yields the overall running time of O(nlogn) >> > >> > >> On Tue, Jun 22, 2010 at 7:48 PM, sharad kumar >> > >> <sharad20073...@gmail.com>wrote: >> > >> > >>> How will you find the subarray whose sum is k in an array of >> negative and >> > >>> positive numbers >> > >> > >>> -- >> > >>> 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> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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.