Algorithms for Coding Interviews in Python/

...

/

Solution: Find Two Numbers That Add Up to "n"

Solution: Find Two Numbers That Add Up to "n"

This review provides a detailed analysis of the different ways to solve the previous challenge.

We'll cover the following...

Solution #1: brute force

Python 3.5
def find_sum(lst, n):
    """
    Function to find two number that add up to n
    :param lst: A list of integers
    :param n: The integer number n
    """
    for i in range(len(lst)):
        for j in range(len(lst)):
            if lst[i] + lst[j] == n and i != j:
                return [lst[i], lst[j]]
# Driver code to test above
if __name__ == '__main__':
    
    print(find_sum([1, 2, 3, 4], 5))

Explanation

This is the most time-intensive, but intuitive solution. Traverse the whole list and for each element in the list, check if any two elements add up to the given number n. So, use a nested for loop and iterate over the entire list for each element.

Time complexity

Since we iterate over the entire list of nn elements, the time complexity is O(n2)O(n^2).

Solution #2: sorting the list

Python 3.5
def binary_search(lst, item):
    """
    Binary Search helper function
    :param lst: A list of integers
    :param item: An item to be searched in the list
    """
    first = 0
    last = len(lst) - 1
    found = False
    
    while first <= last and not found:
        mid = (first + last) // 2
        
        if lst[mid] == item:
            found = mid
        else:
            if item < lst[mid]:
                last = mid - 1
            else:
                first = mid + 1
    
    return found
def find_sum(lst, n):
    """
    Function to find two number that add up to n
    :param lst: A list of integers
    :param n: The integer number n
    """
    lst.sort()
    for j in lst:
        index = binary_search(lst, n - j)
        if index:
            return [j, n - j]
# Driver to test above code
if __name__ == '__main__':
    
    print(find_sum([1, 2, 3, 4], 5))

Explanation

While solution #1 is very intuitive, it is not very time efficient. A better way to solve this is by first sorting the list. Then, for each element in the list, use a binary search to look for the difference between that element and the intended sum. You can implement the binary_search function however you like, recursively or iteratively. So, if the intended sum is n and the first element of the sorted list is a0, then you will conduct a binary search for n-a0 and so on for every a ...