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

Asked

Viewed 108 times

4

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.

2 answers

5


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.

  • 1

    Thank you very much! I managed to understand this logic, it is much simpler than I thought.

5

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.

  • Thanks for the help!

  • @That’s what we’re here for!

Browser other questions tagged

You are not signed in. Login or sign up in order to post.