Check number not a sum of 2 ints on a list

Question

Given a list of integers, I want to check a second list and remove from the first only those which can not be made from the sum of two numbers from the second. So given a = [3,19,20] and b = [1,2,17], I'd want [3,19].

Seems like a a cinch with two nested loops - except that I've gotten stuck with break and continue commands.

Here's what I have:

def myFunction(list_a, list_b):
    for i in list_a:
        for a in list_b:
            for b in list_b:
                    if a + b == i:
                        break
                    else:
                        continue
                    break
                else:
                    continue
            list_a.remove(i)
    return list_a

I know what I need to do, just the syntax seems unnecessarily confusing. Can someone show me an easier way? TIA!

Answer 1

you can try something like that:

a = [3,19,20]
b=  [1,2,17,5]

n_m_s=[]
data=[n_m_s.append(i+j) for i in b for j in b  if i+j in a]

print(set(n_m_s))

print("after remove")

final_data=[]
for j,i in enumerate(a):
    if i not in n_m_s:
        final_data.append(i)

print(final_data)

output:

{19, 3}
after remove
[20]

Answer 2

You can do it by first creating all possible sum combinations, then filtering out elements which don't belong to that combination list

Define the input lists

>>> a = [3,19,20]
>>> b = [1,2,17]

Next we will define all possible combinations of sum of two elements

>>> y = [i+j for k,j in enumerate(b) for i in b[k+1:]]

Next we will apply a function to every element of list a and check if it is present in above calculated list. map function can be use with an if/else clause. map will yield None in case of else clause is successful. To cater for this we can filter the list to remove None values

>>> list(filter(None, map(lambda x: x if x in y else None,a)))

The above operation will output:

>>> [3,19]

You can also write a one-line by combining all these lines into one, but I don't recommend this.

Answer 3

Comments on code:

• It's very dangerous to delete elements from a list while iterating over it. Perhaps you could append items you want to keep to a new list, and return that.
• Your current algorithm is O(nm^2), where n is the size of list_a, and m is the size of list_b. This is pretty inefficient, but a good start to the problem.
• Thee's also a lot of unnecessary continue and break statements, which can lead to complicated code that is hard to debug.
• You also put everything into one function. If you split up each task into different functions, such as dedicating one function to finding pairs, and one for checking each item in list_a against list_b. This is a way of splitting problems into smaller problems, and using them to solve the bigger problem.

Overall I think your function is doing too much, and the logic could be condensed into much simpler code by breaking down the problem.

Another approach:

Since I found this task interesting, I decided to try it myself. My outlined approach is illustrated below.

1. You can first check if a list has a pair of a given sum in O(n) time using hashing:

def check_pairs(lst, sums):
    lookup = set()

    for x in lst:
        current = sums - x
        if current in lookup:
            return True
        lookup.add(x)

    return False

2. Then you could use this function to check if any any pair in list_b is equal to the sum of numbers iterated in list_a:

def remove_first_sum(list_a, list_b):
    new_list_a = []

    for x in list_a:
        check = check_pairs(list_b, x)
        if check:
            new_list_a.append(x)

    return new_list_a

Which keeps numbers in list_a that contribute to a sum of two numbers in list_b.

3. The above can also be written with a list comprehension:

def remove_first_sum(list_a, list_b):
    return [x for x in list_a if check_pairs(list_b, x)]

Both of which works as follows:

>>> remove_first_sum([3,19,20], [1,2,17])
[3, 19]
>>> remove_first_sum([3,19,20,18], [1,2,17])
[3, 19, 18]
>>> remove_first_sum([1,2,5,6],[2,3,4])
[5, 6]

Note: Overall the algorithm above is O(n) time complexity, which doesn't require anything too complicated. However, this also leads to O(n) extra auxiliary space, because a set is kept to record what items have been seen.

Answer 4

You can do like this,

In [13]: from itertools import combinations
In [15]: [item for item in a if item in [sum(i) for i in combinations(b,2)]]
Out[15]: [3, 19]

combinations will give all possible combinations in b and get the list of sum. And just check the value is present in a

Edit

If you don't want to use the itertools wrote a function for it. Like this,

def comb(s):
    for i, v1 in enumerate(s):
        for j in range(i+1, len(s)):
            yield [v1, s[j]]

result = [item for item in a if item in [sum(i) for i in comb(b)]]