Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?
We can compute all combinations of 2 elements in the list and then verify if they adds up to k.
def solve(list_of_numbers, k): for index_1, element_1 in enumerate(list_of_numbers): for index_2, element_2 in enumerate(list_of_numbers): if index_1 != index_2: if element_1 + element_2 == k: return True return False
This run in O(N²) due to the nested loop.
As we iterate over the list we can store in a set the elements we’ve seen so far.
We can then check if weather or not we have seen the complement (difference with k) before.
def solve(list_of_numbers, k): seen = set() for element in list_of_numbers: complement = k - element if complement in seen: return True else: seen.add(element) return False
This run in O(N) since we iterate over the list once and lookup in a set is O(1).