comment on

Hi Monks

The following algorithm seems to need 4+N+M memory ... and therefore fulfills the challenge :-)

val = N1 + M1
loop

for all i, j: if (Ni+Mj == val) print (Ni+Mj)
nextval = val
for all i, j: if ((Ni+Mj)>val) && ((Ni+Mj) < nextval) => nextval = (Ni + Mj)
if (val == nextval) => exit # we are finished
val = nextval

goto 2.

So in additon to N and M, you need the constant space for 4 variables (i, j, val, nextval) and for the temporary sums. :-)
However the runtime would be O(N^2*M^2) (*) - so I wouldn't consider it efficient ;-)

Rata

(*) 2 * N * M for the inner loop - and a maximum N * M for the outer one

note: the restriction that N and M are sorted can easily be dropped with the algorithm above (just replace line 1 with lines 2.2.-2.5)

update: Limbic~Region just told me that blokhead posted nearly the same solution before (he needs one variable more, which doesn't affect the complexity O((NM)^2). ... I didn't want to waste bandwidth, but I fear duplicated solutions are the risk if one is not cheating ;-)

In reply to Re: Challenge: Sorting Sums Of Sorted Series by Ratazong
in thread Challenge: Sorting Sums Of Sorted Series by Limbic~Region

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


We don't bite newbies here... much
	PerlMonks