Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Fastest algorithm Discussion

Name: Anonymous 2008-04-04 16:43

Anyway just for fun and learning I have been messing with algorithms in my head.  Here is the problem:  There is a set of numbers N, Is there a subset of exactly two of them which equal a number Z. 

So for instance, 1,4,6,125,185 and the sum 129.  Would return true. 

What is the fastest exact way to do this for arbitrarily large numbers?

I know one method is to take the largest and smallest (1,129) and move each one up or down depending on < or >.  This method takes O(N) time.

What are the faster algs for this?

Name: Anonymous 2008-04-04 17:28

Here is a fast solution that requires cons:


(define (algorithm l sum)
 (cons sum (algorithm l sum)))

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List