Given a list of n integers, write a function to determine if any two sum to k
Three possible solutions:
-
Naive. Compering all pairs of number. Perf O(n^2) Mem O(1)
def find_pair_sum(lst, k): if lst is None: return for i in xrange(0, len(lst)): for j in xrange(0, len(lst)): if lst[i] + lst[j] == k: yield lst[i], lst[j] for p in find_pair_sum([1,2,3,4,9,5], 6): print p
-
Sorting and finding element with Binary Search. Perf O(nlgn) Mem O(1)
def _binary_search_rec(lst, start, end, elem): if start <= end: mid = (end - start) / 2 + start if lst[mid] == elem: return True elif lst[mid] < elem: return _binary_search_rec(lst, mid + 1, end, elem) else: return _binary_search_rec(lst, start, mid - 1, elem) def binary_search(lst, elem): if lst is None: return False return _binary_search_rec(lst, 0, len(lst) - 1, elem) def find_pair_sum(lst, k): if lst is None: return lst.sort() for elem in lst: if binary_search(lst, k - elem): yield elem, k - elem for p in find_pair_sum([1,2,3,4,9,5], 6): print p
-
Using Hash set. Perf O(n) Mem O(n)
def find_pair_sum(lst, k): if lst is None: return s = set(lst) for elem in s: if k - elem in s: yield elem, k - elem for p in find_pair_sum([1,2,3,4,9,5], 6): print p
Written by lukas
Related protips
2 Responses
![](https://coderwall-assets-0.s3.amazonaws.com/uploads/user/avatar/108847/0_KMzyHBPQgoG8uPMoKyqfHzzvxf5K2P4o-Y3iHztv8Wl81cfEpxLKQv6UlGL77NJ6lscCFthAxleN.jpeg)
I don't understand how III can be Pref O(n).
I think it would be O(n^2) or maybe O(nlgn). The second loop is hidden in the search for the (k-elem) element in the S set. This second loop would take O(n) or at best O(lgn) time depending on how the code was written by the system programmers (straight for loop or binary hash).
What am I missing?
over 1 year ago
·
![](https://coderwall-assets-0.s3.amazonaws.com/uploads/user/avatar/67883/b2bc42f69510d6a1d2c9cde1c2214d24.jpg)
@jratcliff python set is implemented as a hashset finding element takes O(1)
over 1 year ago
·
Have a fresh tip? Share with Coderwall community!
Post
Post a tip
Best
#Python
Authors
Sponsored by #native_company# — Learn More
#native_title#
#native_desc#