may be right, but how about this:
On input sorted arrays L and R
output[0] = L[0]+R[0]
i=0
j=0
p=0
for n=1 to k-1
if i+1>size[L]
if j+1>size[R]
error "can't get k sums"
else
j=j+1
else if j+1>size[R]
i=i+1
else if
else if L[i+1]+R[j]>R[j+1]+L[i]
j = j+1
else
i=i+1
output[k] = L[i]+R[j]
I'm fairly certain this is correct, since arrays are sorted and you are
allowed to output duplicate sums, because this is exactly the merge
type procedure described by Sri. The only problem is that this is a
O(k) solution and you said O(k lg k) was optimal. Thus, I am fairly
certain you misstated some part of the problem.
I think what's missing is that the same element from each array can be
involved in multiple sums and sums can be of an arbitrary number of
numbers.
You can add this capability by keeping an array of cumulative sums of
your minimum sums (i.e. cumsum[n] = cumsum[n-1]+output[n]), and a way
to mark them when you use them, then comparing the two sums that are
compared above with each of with:
-the element of the left array plus the first unmarked elem of the
cumsum array
-the element of the right array plus the first unmarked elem of the
cumsum array
if either is the next minimum sum, use it.
I recommend using a linked list (of the variety with a pointer from
head to tail) with a reference moving across it as the means of marking
(mark by moving reference to right). . .this makes accessing the first
unmarked element take O(1), and makes adding new cumsums to it O(1).
If the reference advances to the list head again, refuse to compare
that value or use it (again). Also, if either of the pointers to L or
R are incremented, reset this reference to the head of the list.
Now sums using an arbitrary number of numbers and repetitions can be
used.
And yet the algorithm still seems to take only O(k). Correct me if I'm
wrong.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
