If any two items in a list is equal to a given number

Question

I just subscribed to the daily coding problems and received my first today.

The problem is:

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.

This is what I came up with:

def anyequalto(x, y):
 for i in x:
 if y - i in x:
 return True
anyequalto([10, 15, 3, 7], 17)

I was wondering if anyone had any notes or alternatives as I'm very new to Python and programming.

• Solomon Ucko: Your revised code is actually less efficient. There is no point in creating a new list each time.
• Eric Lippert: This puzzle must be making the rounds, because someone posted it on this site a few days ago: codereview.stackexchange.com/questions/208138/…
• SylvainD: Please do not add new code to your question. Your new code has a few aspects that deserve to be reviewed. You can do so in a different follow-up question. Please refer to the rules for that.
• jaxad0127: Your revised code doesn't work correctly with duplicate values. contains_pair_totalling([5, 5], 10) returns false. Sets don't contain duplicates, so your remove call breaks this case.
• AJNeufeld: The original code didn’t work with the sum double any list value, either. anyequalto([5], 10) returns True!

Answer 1

There's a failing case you might have missed. If the target number is exactly twice the value of one of the entries, then you'll wrongly return true.

Test case:

anyequalto([5], 10)

Besides that, try to think of a better name for the function. Perhaps contains_pair_totalling() as a start?

• SimonJ: Didn't think of that. I'd fix this by taking the number it's checking out of the list, then checking it and adding it back for the next run. Any thoughts?
• Toby Speight: Yes, that would be a correct fix. It might not be efficient for very large inputs; I don't know whether that's a concern.
• Especially Lime: @SimonJ you wouldn't need to add it back - if it is part of a pair summing to k then there won't be a next run, and if it isn't then it won't affect future runs.

Answer 2

Return value

Adding a few tests, we have:

print(anyequalto([10, 15, 3, 7], 17))
print(anyequalto([10, 15, 3, 7], 18))
print(anyequalto([10, 15, 3, 7], 19))

giving

True
True
None

The None value seems a bit unexpected to me. We'd probably want False to be returned in that particular case.

Also, even if you expect None to be returned in that case, the Python Style Guide recommends being explicit for that (emphasis is mine):

Be consistent in return statements. Either all return statements in a function should return an expression, or none of them should. If any return statement returns an expression, any return statements where no value is returned should explicitly state this as return None, and an explicit return statement should be present at the end of the function (if reachable).

Names, documentation and tests

The variables names could be clearer.

Also, the function behavior can be described in a docstring.

Finally, it could be worth writing tests for it.

You'd get something like:

def anyequalto(num_lst, n):
 """Return True if 2 numbers from `num_lst` add up to n, False otherwise."""
 for i in num_lst:
 if n - i in num_lst:
 return True
 return False
TESTS = [
 # Random tests cases
 ([10, 15, 3, 7], 17, True),
 ([10, 15, 3, 7], 18, True),
 ([10, 15, 3, 7], 19, False),
 # Edge case
 ([], 0, False),
 ([], 1, False),
 # Same value
 ([5, 5], 10, True),
 ([5], 10, True),
 # Zero
 ([5, 0], 0, True),
 ([5, 0], 5, True),
 ([5, 0], 2, False),
]
for (lst, n, expected_res) in TESTS:
 res = anyequalto(lst, n)
 if res != expected_res:
 print("Error with ", lst, n, "got", res, "expected", expected_res)

Data structure

At the moment, you can iterate on the list (via the in check) for each element of the list. This leads to an O(n2) behavior.

You can makes t hings more efficient by building a set to perform the in test in constant time and have an overall O(n) behavior.

def anyequalto(num_lst, n):
 """Return True if 2 numbers from `num_lst` add up to n, False otherwise."""
 num_set = set(num_lst)
 for i in num_set:
 if n - i in num_set:
 return True
 return False

Using the Python toolbox

The solution you are using could be written in a more concise and efficient way using the all or any builtin.

You have something like:

def anyequalto(num_lst, n):
 """Return True if 2 numbers from `num_lst` add up to n, False otherwise."""
 num_set = set(num_lst)
 return any(n - i in num_set for i in num_set)

• SimonJ: The any builtin is something I hadn't seen yet. Since someone pointed out that if the value of n is the exact double of an item in num_lst. How would that work out with any? If possible.
• Eric Duminil: anyequalto([5], 10) should be False, so you cannot simply create num_set like this. You need to iterate over the numbers, check if n-i is in the set and only then add i to the set.
• Eric Duminil: And [5, 0], 0 should be False.
• SylvainD: I relied on the original code behavior and made sure I didn't change it while making it more explicit via the corresponding test cases. Maybe I should have hilighted it as a bug (I do not quite remember how the problem was expressed initially).
• SylvainD: Also, if I were to re-implement it based on that new behavior, I'd probably just use a Counter...

Answer 3

Here's a fix to the edge case. We want to check explicitly that we have a valid solution, which means that we want something akin to any2 instead of any (since if we have just a single match then we have the problem case).

def anyequalto(numbers, k):
 number_set = set(numbers)
 solutions = [num for num in numbers
 if k - num in number_set]
 return len(solutions) > 1

This fixes the edge case and still retains O(n) runtime since it uses a set.

>>> anyequalto([5], 10)
False

Aside

Right now this produces a list with the list comprehension used to generate solutions which one might argue is needlessly inefficient. I couldn't think of a stylistically good way to assert that a generator has more than one element aside from checking for StopIteration which I think is kinda clunky.

• spectras: next(iterator, sentinel) will return sentinel if the iterator is exhausted.
• Eric Duminil: Nice, it also works with anyequalto([5, 5], 10) # True.

Answer 4

• As others have mentioned, your code could be more efficient with set lookup.
• It should return False with [5] and 10 as input parameters.
• Python method names are written in snake_case.
• Python is a dynamic language, which means method names and parameter names are very important. They make it easier to read your code and understand it again 6 months after having written it. x sounds like an unknown object or a float, not like a list of integers.

Here's a possible way to write the method:

def contains_pair_with_given_sum(numbers, desired_sum):
 unique_numbers = set()
 for number in numbers:
 if (desired_sum - number) in unique_numbers:
 return True
 unique_numbers.add(number)
 return False

It outputs:

contains_pair_with_given_sum([5, 10, 7], 12)
# True
contains_pair_with_given_sum([5], 10)
# False

You could also use the fact that a pair of integers is truthy in Python and return the pair when found:

def find_pair_with_given_sum(numbers, desired_sum):
 unique_numbers = set()
 for number in numbers:
 if (desired_sum - number) in unique_numbers:
 return (number, desired_sum - number)
 unique_numbers.add(number)

It outputs:

find_pair_with_given_sum([5, 10, 7], 12)
# (7, 5)
find_pair_with_given_sum([5], 10)
# None

Answer 5

1. for a much faster way to check if a number is in some container, use a set(): anyequalto({10, 15, 3, 7}, 17). even if you have to convert from a list first, it will still be faster to do that once rather than linearly search the list each iteration. This will make your function O(n) rather than O(n^2)

2. choose more expressive variable names that x and y. something like numbers and k j

3. If you want to write this in a more functional style, you could do:

   def anyequalto(numbers, k):
    numbers = set(numbers)
    return any((k-num) in numbers
    for num in numbers)
   

   Because any will terminate early if the generator produces a true value, this will be very similar in speed to an iterative solution.

• Graipher: It should be any(k in numbers for num in numbers), not any(for num in numbers k in numbers).
• Eric Duminil: anyequalto([5], 10) should be False.

Answer 6

A simple solution would use any and itertools.combinations

from itertools import combinations
def anytwoequalto(numbers, k):
 return any(((i + j) == k) for i, j in combinations(numbers, 2))

itertools.combinations iterates over the given object returning tuples with the given number of items in them with no repetitions. eg.

combinations('ABCD', 2) =>
 (('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D'))

any returns True if any of the expressions ((i + j) == k) evaluate to True

If you wish to consider that an item can be added to itself, use combinations_with_replacement instead.

Note: depending on the version of Python you are using, you may need to add extra parentheses (()) around the expression inside the any call.

Hope this makes sense.