I gave this one a shot, and the code works. Am I on the right track? How can the code be improved? Also, I am unaware of how to determine if this would be linear time or not. Could someone maybe break that determination down for me?
''' Problem statement: Find pairs in an integer array whose sum is equal to n (bonus: do it in linear time) @author: Anonymous3.1415 ''' def pair_sum_to_n(integer_list, n): pairs = [] #checks for the occurence of halfs if not n % 2: if integer_list.count(n/2) > 1: pairs.append((n/2, n/2)) integer_set = set(integer_list) - {n/2} #finds pairs of integers where x + (n - x) = n for x in integer_set: if (n - x) in integer_set: if (n - x, x) not in pairs: pairs.append((x, n - x)) return pairs integer_list = list(map(int, raw_input().strip().split(" "))) pairs = pair_sum_to_n(integer_list, 10) print(pairs)