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.

[ghostdog74]

efficiency not taken into consideration:

s = [2, 5, 7, 9, 13, 15]
n = 16 
l = [n] * len(s)
if n in s:
    print "16 + 0"
else:
    r = [ operator.sub(*i) for i in zip(l,s) ]
    print set(s).intersection(set(r))
 

I have not tried on other variations, so this method may not be what you want

[lastsurvivor]

buldu=0;
left = 0;
right= Length-1;
 
while (left == right || buldu==1) {
    if a[left]+ a[right] > KEY
    right--;
    else if a[left]+ a[right]<KEY
    left++;
    else if a[left]+ a[right]==KEY
    buldu = 1; 
}

best optimized i coud find.

[bvdet]

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.

Assuming your sequence will always contain unique numbers (no duplicates):

s = [2, 5, 7, 9, 13, 15]
 
result = 16
 
# count the number of iterations
i = 1
 
# no need to check the last element in the list
while len(s) > 1:
    print i
    n = result - s[0]
    if n in s:
        print '%d + %d = %d' % (s[0], n, result)
        # remove 'n' from list
        s.remove(n)
    # remove first element from list
    s = s[1:]
    i += 1

Output:
>>> 1
2
3
7 + 9 = 16
4
>>>

If your sequence is always increasing in value, you can stop iterating after result/s[0] = 1.

[bartonc]

Assuming your sequence will always contain unique numbers (no duplicates):

s = [2, 5, 7, 9, 13, 15]
 
result = 16
 
# count the number of iterations
i = 1
 
# no need to check the last element in the list
while len(s) > 1:
    print i
    n = result - s[0]
    if n in s:
        print '%d + %d = %d' % (s[0], n, result)
        # remove 'n' from list
        s.remove(n)
    # remove first element from list
    s = s[1:]
    i += 1

Output:
>>> 1
2
3
7 + 9 = 16
4
>>>

If your sequence is always increasing in value, you can stop iterating after result/s[0] = 1.

I like it! But on line 17, instead of recreating/reassigning the list, I'd use

s.pop(0)

as an efficiency improvement.

[bvdet]

I like it! But on line 17, instead of recreating/reassigning the list, I'd use

s.pop(0)

as an efficiency improvement.

You are correct Barton! Thanks.
BTW - Congrats on breaking the 5000 barrier.

[bartonc]

You are correct Barton! Thanks.
BTW - Congrats on breaking the 5000 barrier.

Thank you <takes a deep bow>, thank you very much.

[dmr]

Hi,

I don't know if you're still interested, but a much more efficient algorithm would be to not do a linear search (at least for an arbitrarily large sequence). The following code does a binary search which converges on the two values which would sum to the target value (based on the premise that if no values are repeated and the sequence is increasing then the first value < target/2 < second value).

from math import floor
from math import ceil
from random import choice
 
s = [0]
 
for i in range(1,10000):
  s.append(s[i-1] + choice([1,2,3,4,5]))
 
n = float(raw_input( "Enter a test number: "))
 
testn = int(floor( n/2 ) )
 
oldlistlen = len(s)
listlen = int( floor(len(s) / 2) )
foundit = False
keepgoing = True
i = 0
upperlen = oldlistlen
lowerlen = 0
 
while keepgoing == True:
  print "Testing listlen %d, %d and %d" % (listlen, s[listlen], s[listlen + 1])
  listlentemp = listlen
  i = i + 1
 
  if s[listlen] + s[listlen + 1] == n:
    foundit = True
    keepgoing = False    
 
  elif s[listlen] < testn and s[listlen + 1] > testn:
    print "No solution (<> test)"
    keepgoing = False
 
  elif listlen == 0 or listlen == oldlistlen - 1:
    keepgoing = False
 
  elif s[listlen] > testn:
    upperlen = listlen
    listlen = lowerlen + int( floor( ( upperlen - lowerlen ) / 2 ) )
 
  elif s[listlen] == testn:
    print "No solution (found testn)"
    keepgoing = False
 
  else:
    lowerlen = listlen
    listlen = lowerlen + int( ceil( (upperlen - lowerlen) / 2 ) )
 
if foundit:
  print "Found it after %d iterations at index %d." % (i, listlen)
 
else:
  print "Not found after %d iterations." % (i)
 

Let me know what you think.

[hussainz2000]

Hi,

What is the solution if in case we need to select more than on digit?
for example : in our list [2,5,7,9,13,15] and we need to find 16.
16 = 2+5+9 . and also it might more than 3 digits for example
31 =2+5+9+15 and so on......

Regards

[dmr]

That is a much more difficult problem, which has it's own wikipedia page.