@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
<[email protected]> 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 <[email protected]> wrote:
>
> > @amir
>
> > ur algo works only for positive elements array..
>
> > correct me if m wrong
>
> > On 23 June 2010 00:28, Amir hossein Shahriari <
> > [email protected]> 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
> >> <[email protected]>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 [email protected].
> >>> To unsubscribe from this group, send email to
> >>> [email protected]<algogeeks%[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]<algogeeks%[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.
--
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.
