Given an X number, check if there are 2 elements in a list that together result in X

Question

Problem: The user enters an X number, and a function must check whether two numbers summed within a list, content elements that can be ' ' or integers, results in the user’s X number.

My job:

# Tentei fazer 2 laços fors, para percorrer a soma da lst[0] com os outros, da lst[1] com os outros, etc.

def plus_element(num, lst):
i1 = 0
i2 = 0
for i in range(len(lst)):
    for j in range(len(lst)):
        if isinstance(lst[i1], int) and isinstance(lst[i2], int):
            if lst[i1] + lst[i2] == num:
                print(f'{lst[i1]} + {lst[i2]} é igual ao número {num}.')
                return
        i1 += 1
    if isinstance(lst[i1], int) and isinstance(lst[i2], int):
        if lst[i1] + lst[i2] == num:
            print(f'{lst[i1]} + {lst[i2]} é igual ao número {num}.')
            return
    i2 += 1

The mistake I’m having is that if the list has more than 2 numbers, the function gives error.

# Minha lista
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 
' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 
' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' 
', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' 
', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 5, 2, 10]

The error it presents:

IndexError: list index out of range

Would anyone know to help me? Thanks for your attention.

Answer 1

You don’t have to go through the entire list twice.

Just go from the current index to the end. For example, I start from the first element and test the sum of it with all the others (from the second on).

Then I start from the second element and test the sum of this with the others, but from the third one on. I do not need to test again the sum of the second with the first, as this has been tested previously.

And I go so down to the penultimate, testing the sum of this with the last. So:

lista = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 
' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 
' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
5, 2, 10]

def plus_element(num, lst):
    for i in range(len(lst) - 1): # vou do primeiro ao penúltimo
        for j in range(i, len(lst)): # vou do atual até o último
            n1, n2 = lst[i], lst[j]
            if isinstance(n1, int) and isinstance(n2, int):
                if n1 + n2 == num:
                    print(f'{n1} + {n2} é igual ao número {num}.')
                    return True
    return False

print(plus_element(15, lista)) # True
print(plus_element(1000, lista)) # False

I also made the function return True or False, indicating whether or not it was found. But I prefer that the function does not print anything and only returns the result, and whoever called it does whatever they want with the result (print the message, etc):

def plus_element(num, lst):
    for i in range(len(lst) - 1):
        for j in range(i, len(lst)):
            n1, n2 = lst[i], lst[j]
            if isinstance(n1, int) and isinstance(n2, int):
                if n1 + n2 == num:
                    return (n1, n2) # retorna uma tupla com os números
    return None # não encontrou

num = 15
result = plus_element(num, lista)
if result is not None:
    n1, n2 = result
    print(f'{n1} + {n2} é igual ao número {num}.')
else:
    print(f'Não foi possível encontrar 2 números que somam {num}')

---

If it’s not an exercise, there’s a simpler way, using the module itertools:

from itertools import combinations

def plus_element(num, lst):
    for n1, n2 in combinations(lst, 2):
        if isinstance(n1, int) and isinstance(n2, int):
            if n1 + n2 == num:
                return (n1, n2) # retorna uma tupla com os números
    return None # não encontrou

combinations already returns all combinations of the list elements.

---

And if there are several elements that are not numbers, maybe it is better to filter only the elements you want, and only then test the combinations between them:

def plus_element(num, lst):
    for n1, n2 in combinations(filter(lambda e: isinstance(e, int), lst), 2):
        if n1 + n2 == num:
            return (n1, n2) # retorna uma tupla com os números
    return None # não encontrou

In case I used filter to take only the elements that are numbers, so the number of combinations already decreases enough in your case.

Answer 2

Colleague @hkotsubo already explained the problem and showed solutions, and I take this opportunity to show another way to solve the problem that is also very efficient, since it only goes through the list once:

def plus_element(num, lst):
    encontrados = set()
    for elem in lst:
        if isinstance(elem, int) and (num - elem) in encontrados:
            return num - elem, elem
        encontrados.add(elem)
    return None

See code working on Ideone

This solution uses a set additional to mark the elements already found, so that whenever you find a new element you can know immediately if the pair of the new element has already left, and if it has left has a valid solution.

Example: You want the sum to 7. Go through 2 and record that number, then go through 5 and you know that the pair is 2 because 7 - 5 is 2. Since that number has already left you have a valid pair, the current number and its pair.

In the code the encontrados = set() is the set which records the numbers that have already been released and the (num - elem) in encontrados is what checks if the pair of the current number has already left.