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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.