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