TADM2E 4.6

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