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?
I wrote my code like this and i got right answer for the above input
x=[10,15,3,7] y=17 for i in x: if (y-i) in x: print(True) break
And checked others code too to know that i was right or wrong and many used sets in their code as
def sum_exists(l,k): s = set() for x in l: if k-x in s: return True s.add(x) return False
I still don’t understand the difference between their code and mine.Am i wrong?
What is the use of sets differ from my code?
Advertisement
Answer
Your code iterates the list once and checks the list with in
– in total you do lots of runs through the list.
You can do it in one pass with the additional space of a set:
x = [10,15,3,7] y = 17 s = set() for i in x: # go throug the list once if y-i in s: return True s.add(i) return False
Checking if something is in a set is O(1) (constant time) checking in in list is O(n) (linear time). If you have a list of 1 million uniqe numbers that do not add up to y
your code iterates the list of 1 million times 1000001 times – once to go through and 1000000 times to check. Total time is O(1000001*1000000)
If you use a set it is O(1000000)+1000000*O(1) which is “better” but it takes some additional space/memory.