CODEWITHSUNDEEP
python
tlanigan
tlanigan

Reputation: 979

How to check if N can be expressed as sum of two other numbers in specific list

I have a list:

l = [1,3,4,6,7,8,9,11,13,...]

and a number n.

How do I efficiently check if the number n can be expressed as the sum of two numbers (repeats are allowed) within the list l.

If the number is in the list, it does not count unless it can be expressed as two numbers (e.g for l = [2,3,4] 3 would not count, but 4 would.

This, embarrassingly, is what I've tried:

def is_sum_of_2num_inlist(n, num_list): 

num_list = filter(lambda x: x < n, num_list)

for num1 in num_list:
    for num2 in num_list:
        if num1+num2 == n:
            return True

return False

Thanks

Upvotes: 4

Views: 2046

Answers (4)

Learner
Learner

Reputation: 5302

If I got the OP's concern then-

As the question says repeats are allowed within the list l this process i think is good though a bit slower.So if you need to count the occurances along with the existence of a condition then go with this answer but if you want a bolean esixtence check the go with the others for the mere performance issue nothing else.

You can use itertools.combinations. It will give you all the combinations, not permutations. Now you can just use the sum function to get the sum.

from itertools import combinations

l = [1,3,4,6,7,8,9,11,13]
checks = [4,6] #these are the numbers to check

for chk in checks:
    for sm in  combinations(l,2):
        if chk == sum(sm): #sum(sm) means sum(1,3) for the first pass of the loop
            #Do something

Upvotes: 0

user6214276
user6214276

Reputation:

If the list is ordered you could use two variables to go through the list, one starting at the beginning of the list and one at the end, if the sum of the two variables is greater than N you assign to the variable at the end the values that precedes it, if the sum is less than N you assign to the variable at the beginning the following value in the list. If the sum is N you've found the two values. You can stop when the two variables meet eachother.

If the list is not ordered you start from the beginning of the list and use a variable x to go through the list. You'll need another structure like an hashset or another structure. At every step you'll look up in the second hashset if the value N-x is in there. If there is, you've found the two numbers that add up to N. If there isn't you'll add N-x in the hashset and assign to x the following value. I recommend using an hashset because both the operations of looking up and inserting are O(1).

Both algorithms are linear

I'm sorry I couldn't write directly the code in python because I don't use it.

As I said in the comment HERE there's a video in wich your problem is solved

Upvotes: 1

mVChr
mVChr

Reputation: 50195

def summable(n, l):
    for v in l:
        l_no_v = l[:]
        l_no_v.remove(v)
        if n - v in l_no_v:
            return True
    return False

EDIT: Explanation...

The itertools.cominations is a nice way to get all possible answers, but it's ~4x slower than this version since this is a single loop that bails out once it gets to a possible solution.

This loops over the values in l, makes a copy of l removing v so that we don't add v to itself (i.e. no false positive if n = 4; l = [2, 1]). Then subtract v from n and if that value is in l then there are two numbers that sum up to n. If you want to return those numbers instead of returning True just return n, n - v.

Upvotes: 3

brianpck
brianpck

Reputation: 8254

Although you can check this by running through the list twice, I would recommend for performance converting the list to a set, since x in set() searches in linear time.

Since n can be the sum of the same number, all you have to do is iterate through the set once and check if n - i occurs elsewhere in the set.

Something like the following should work.

>>> def is_sum_of_numbers(n, numbers):
...     for i in numbers:
...         if n - i in numbers:
...             return True
...     return False
...
>>>
>>>
>>> numbers = {2,7,8,9}
>>> is_sum_of_numbers(9, numbers) # 2 + 7
True
>>> is_sum_of_numbers(5, numbers)
False
>>> is_sum_of_numbers(18, numbers) # 9 + 9
True

Upvotes: 2

Related Questions