Can it be made faster, and I am a newbie to complexity but I'm pretty sure the average case for this would be O(n). Am I wrong? Output for the first list should be: (1,9), (2,8), (5,5), (-11,21)
The program finds pairs of an array whose sum is equal to ten.
#find pairs of an array whose sum is equal to ten
#bonus do it im linear time
list1 = [1,1,2,1,9,9,5,5,2,3,745,8,1,-11,21]
list2 = [1,1,1,1,9,9,9,9,2,8,8,8,2,2,0,0,0]
list3 = ["dog", "cat", "penguin", 9, 1]
list4 = []
def find_pairs_sum_n(list1, n):
set1 = set(list1)
history = set()
if not list1:
print("list is empty")
raise StopIteration
if not all(isinstance(n, int) for n in list1):
print("list must contain only integers")
raise StopIteration
for x in set1:
history.add(x)
if (n - x) in set1 and (n-x) not in history:
yield (x, n - x)
elif x == n/2 and list1.count(n/2) > 1:
yield (int(n/2), int(n/2))
x = find_pairs_sum_n(list1, 10)
for i in x:
print(i)
y = find_pairs_sum_n(list2, 10)
for i in y:
print(i)
z = find_pairs_sum_n(list3, 10)
print(next(z))
w = find_pairs_sum_n(list4, 10)
print(next(w))
