Skip to content
Advertisement

What makes the difference by creating a set in this code?

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.

Advertisement