# TADM2E 4.6

From Algorithm Wiki

subtract n from the first set, sort both sets in O(nlogn). find the first equal under n

One more approach to solve the above problem

1. Sort S1; (n log n) 2. Sort S2; (n log n) 3. beg := S1[0] end := S2[m-1] 4. while (beg < n && end >=0 ) O(n) if S1[beg] + S2[end] > sum then end-- else if S1[beg] + S2[end] < sum beg++ else return (beg, end) End Loop Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)

--Max 07:04, 25 June 2010 (EDT)

A third approach

1. Sort S1; O(n log n) 2. for i=0 to n-1 val := x - S2[i] if binary_search(S1, val) O(log n) return (val, S2[i]) End Loop

Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)

There is also a linear solution, O(n).

For i in 1..n Check if x - S1[i] exists in seen numbers set T. Return true or add S1[i] to T. Check if x - S2[i] exists in T. Return true or add S2[i] to T. Return false