To find if a pair of elements exists (one or more) from two sets of same size that equal a predefined sum.

import time
import random
def twosetsum(S1,S2):
sum = 18000000
n = m = len(S2)
start = 0
end = m-1
while start < n and end >= 0 : #O(n)
if S1[start] + S2[end] > sum :
end = end-1
elif S1[start] + S2[end] < sum :
start = start+1
else:
return 1
start = time.strftime('%s')
S1 = range(1,9000001) #O(nlgn) sorted list
S2 = range(1,9000001) #O(nlgn) sorted list
value = twosetsum(S1,S2)
if value == 1 :
print "Yes there is a pair"
else:
print "No there is no pair"
end = time.strftime('%s')
time = int(end) - int(start)
print "Time to execute the Algorithm =", time ,"Second(s)"

OUTPUT:

labuser@ubuntu:~$ python twosetsum.py

Yes there is a pair

Time to execute the Algorithm = 8 Second(s)

Input : sum = 19000000

labuser@ubuntu:~$ python twosetsum.py

No there is no pair

Time to execute the Algorithm = 8 Second(s)

overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)

### Like this:

Like Loading...

*Related*