Last Updated: August 01, 2023
·
942

# Given a list of n integers, write a function to determine if any two sum to k

Three possible solutions:

1. 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``````
2. 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``````
3. 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``````

337.7K
13

301.3K
24

### Emulate do-while loop in Python

253.5K
5

#### 2 Responses

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 ·

@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!

Best #Python Authors
terrasea
337.7K
cheglastgnat
301.3K
saji89
253.5K
lotia
206.4K
Awesome Job