Challenges on sorting and searching

Challenge 1: Find two numbers that add up to "n"

Problem statement

In this problem, you have to implement the find_sum(lst, n) function which will take a list lst and number n as inputs and return two numbers from the list that add up to n.

Solutions

Solution 1: brute force

find_sum.py

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))

Complexity

• Time complexity: O(n^2)

Solution 2: binary search

binary_search.py

def insertion_sort(lst):
    for i in range(len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key


def binary_search(
    lst,
    left,
    right,
    key,
):
    while left < right:
        mid = left + (right - left) // 2
        print("left", left)
        print("right", right)
        print("mid", mid)

        if lst[mid] == key:
            return mid
        elif lst[mid] < key:
            left = mid + 1
        else:
            right = mid - 1
    return -1


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
    """

    print("lst (before):", lst)
    insertion_sort(lst)  # sort lst first
    print("lst (after):", lst)

    for i in range(len(lst)):
        print("i", i)
        find_num = n - lst[i]
        print("find_num", find_num)
        find_num_index = binary_search(lst, 0, len(lst), find_num)
        if find_num_index != -1 and i != find_num_index:
            return [lst[i], lst[find_num_index]]
        print("=" * 20)

    # return False # if you need to give a feedback when not found

Complexity

• Time complexity: O(nlog(n))

Solution 3: using a dictionary

using-a-dictionary-or-python-set.py

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
    """

    found_values = {}
    for ele in lst:
        try:
            found_values[n - ele]
            return [n - ele, ele]
        except:
            found_values[ele] = 0

    return False


def find_sum_v2(lst, n):
    """
    Function to find two number that add up to n
    :param lst: A list of integers
    :param n: The integer number n
    """

    found_values = set()
    for ele in lst:
        if n - ele in found_values:
            return [n - ele, ele]

        found_values.add(ele)

    return False


# Driver code to test above
if __name__ == "__main__":

    print(find_sum([1, 2, 3, 4], 5))
    print(find_sum([1, 21, 3, 14, 5, 60, 7, 6], 81))

    print(find_sum_v2([1, 2, 3, 4], 5))
    print(find_sum_v2([1, 21, 3, 14, 5, 60, 7, 6], 81))

Complexity

• Time complexity: O(n)