efficient algorithm [Merged]

[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.

[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.

[weaknessforcats]

Start at the right.

[JosAH]

Start at the right.

Not necessarily so: if n is near the smallest element in s then it's better to
start at the left.

kind regards,

Jos

[sicarie]

::subscribing::

[JosAH]

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.

You asked exactly this same question in the C/C++ forum. Do you want me
to merge both threads and move them to the 'software development' forum?

Double posting is considered a nono; don't do that anymore.

kind regards,

Jos

[sovixi]

any code sugestions how to do it????

[JosAH]

any code sugestions how to do it????

Nope, we don't do code here but here's a hint: because set s is sorted in
ascending order you can find two indexed l and h (h == l+1) such that
s[l] <= n and s[h] >= n; You can find l and h in O(log(|s|) where |s| is the
size of set s.

repeat the following (while applicable)
x= s[l]+s[h]
if (x == n) found solution
else if (x < n) h= h+1
else l= l-1

This needs O(|s|) additions at most so voila: problem solved.

kind regards,

Jos

[sovixi]

thanks a lot for your help.

Ps I have posted this topic on various forums while looking for an answer. Sorry for that.

[JosAH]

thanks a lot for your help.

Ps I have posted this topic on various forums while looking for an answer. Sorry for that.

You're welcome of course and don't mention those double posts: I closed your
thread in the java forum. I think I'll delete it now.

kind regards,

Jos