Bdtyktl

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.

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(n²) 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)

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?

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.

   
   

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.

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.