# Difference between revisions of "TADM2E 4.6"

From Algorithm Wiki

Line 33: | Line 33: | ||

<pre> | <pre> | ||

For i in 1..n | For i in 1..n | ||

− | Check if x-S1[i] exists in seen numbers set T. | + | Check if x - S1[i] exists in seen numbers set T. |

Return true or add S1[i] to T. | Return true or add S1[i] to T. | ||

− | Check if x-S2[i] exists in T. | + | Check if x - S2[i] exists in T. |

Return true or add S2[i] to T. | Return true or add S2[i] to T. | ||

Return false | Return false | ||

</pre> | </pre> |

## Latest revision as of 18:57, 28 November 2018

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