efficient algorithm

[sovixi]

Hey I'm looking for a solution to the below question. Any recommendations on how to write this algorithm???
Thanks:


You are given a sequence s of numbers, in increasing order, for example:

s = 2, 5, 7, 9, 13, 15.

You are also given a number n, say n = 16. You have to try to find two numbers x and y from s, such that x+y = n, if such numbers exist. In this example, you could take x = 7 and y = 9.

However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this.

[paddy3118]

Originally Posted by sovixi

Hey I'm looking for a solution to the below question. Any recommendations on how to write this algorithm???
Thanks:


You are given a sequence s of numbers, in increasing order, for example:

s = 2, 5, 7, 9, 13, 15.

You are also given a number n, say n = 16. You have to try to find two numbers x and y from s, such that x+y = n, if such numbers exist. In this example, you could take x = 7 and y = 9.

However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this.

The following Python 2.5 program works:

s = [2, 5, 7, 9, 13, 15]
ss = set(s)
mn = s[0]
n = 16
mx = n - mn

for x in s:
    if x > mx:
        # gone over the max value in s allowed
        break
    if n - x in ss:
        print "Using only these numbers:", s
        print "%s + %s == %s" % (x, n-x, n)
        break

It gives the following result when run:

Using only these numbers: [2, 5, 7, 9, 13, 15]
7 + 9 == 16

- Paddy.

[WingedPanther]

Easy solution: load you data into an array
sarray = [2,5,7,9,13,15]
i = 0
j = 5
Then start adding sarray[i] + sarray[j] and comparing to the desired result. if too low, increment i. if too high, decrement j. wrap it in a for loop where i<j is required and you're done.

The key requirement is the number of additions to perform, that means each time you perform an addition, you MUST eliminate one of the numbers in the list.

Paddy's solution is clever, in that addition is not even used as an operation.

[paddy3118]

I started looking at the corner cases and thought "what if the list of numbers has duplicates"? This lead me to update my solution use an implementation of a bag (also known as a multiset), instead of a set in the original.

Here is the extended program:

def add2x(s, n):
    ss = set(s)
    mn = s[0]
    mx = n - mn
    print "Using only these numbers:", s
    for x in s:
        if x > mx:
            # gone over the max value in s allowed
            break
        if n - x in ss:
            print "%s + %s == %s" % (x, n-x, n)
            return (x, n-x)
    print "Cannot make", n, "from two of the entries"

print "\n# Simple Case"
s = [2, 5, 7, 9, 13, 15]
n = 16
add2x(s, n)

print "\n# But wait..."
s = [2, 5, 7, 9, 13, 15]
assert add2x(s, 10) == (5,5)
print "# this is wrong! Only one 5 is in the list."

def dictasbag(sequence):
    ' Use dict as a bag or multiset'
    from collections import defaultdict

    bag = defaultdict(int)
    for item in sequence:
        bag[item] += 1
    return dict(bag)
    
def add2x_2(s, n):
    sbag = dictasbag(s)
    mn = s[0]
    mx = n - mn
    print "Using only these numbers:", s
    for x in s:
        if x > mx:
            # gone over the max value in s allowed
            break
        sbag[x] -= 1
        needed = n - x
        if needed in sbag and sbag[needed]:
            print "%s + %s == %s" % (x, n-x, n)
            return x, n-x
        sbag[x] += 1
    print "Cannot make", n, "from two of the entries"

print "\n# Using add2x_2"
s = [2, 5, 7, 9, 13, 15]
assert add2x_2(s, 10) == None
s = [2, 5, 5, 7, 9, 13, 15]
assert add2x_2(s, 10) == (5, 5)

And here is the generated output:

# Simple Case
Using only these numbers: [2, 5, 7, 9, 13, 15]
7 + 9 == 16

# But wait...
Using only these numbers: [2, 5, 7, 9, 13, 15]
5 + 5 == 10
# this is wrong! Only one 5 is in the list.

# Using add2x_2
Using only these numbers: [2, 5, 7, 9, 13, 15]
Cannot make 10 from two of the entries
Using only these numbers: [2, 5, 5, 7, 9, 13, 15]
5 + 5 == 10