efficient algorithm

[sovixi]

Hey I'm looking for a solution to the belowe 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.

[Tig201]

This is a rough idea but hopefully it will help

Private Sub Form_Load()
  Dim lst(6) As Integer, Cnt1 As Integer, Cnt2 As Integer
  Dim No As Integer, NoNew As Integer
 
  No = 16
  lst(1) = 2
  lst(2) = 5
  lst(3) = 7
  lst(4) = 9
  lst(5) = 13
  lst(6) = 15
 
  For Cnt1 = 1 To UBound(lst) Step 1
    NoNew = No - lst(Cnt1)
    For Cnt2 = Cnt1 + 1 To UBound(lst) Step 1
      If NoNew = lst(Cnt2) Then
        MsgBox (lst(Cnt1) & "+" & lst(Cnt2) & "=" & No)
        Cnt2 = UBound(lst)
        Cnt1 = UBound(lst)
      End If
    Next Cnt2
  Next Cnt1
End Sub
 

The idea is that you could eliminate the numbers as you go through the list

[Killer42]

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.

I don't think this is possible, unless you add the further constraint that the numbers must be next to each other in the list. (Of course, I'm no mathematician.)

Unless you get sneaky and use subtraction instead of addition, but I doubt that's acceptable.

[Killer42]

This is a rough idea but hopefully it will help
...

Hm... neat little routine. I like it! :)