Function on an array of real numbers that finds out if number in the array is composed for every number in array

Question

We have a set/array M of real numbers. A number r in M is composed if there are s and t in M with r = s + t. The goal is to find an algorithm (in pseudocode) that runs in O(n^2), that decides for every r in M if the r is composed or not. The array is sorted in ascending order.

I have no clue how to find a algorithm in given time complexity. Thanks in advance for every input given

Answer 1

Since O(N^2) is permissible, you can simply use two loops to check the sums of all pairs. Hash all numbers in a map and decrement their count if a pair is found. If all numbers have 0 count in the end, it means that a sum pair was found for each element. Simple pseudocode would be:

def func(array):
    map = {}
    n = len(array)
    result = [false]*n
    for i in array:
        map[i] += 1

    for i in range(n):
        for j in range(n):
            temp = array[i]+array[j]
            if temp in map and map[temp] > 0:
                map[temp] -= 1

    for i in range(n):
        key = array[i]
        if key in map and map[key] == 0:
            result[i] = true

    return result