# Difference between revisions of "TADM2E 4.6"

From Algorithm Wiki

(Recovering wiki) |
|||

(One intermediate revision by the same user not shown) | |||

Line 28: | Line 28: | ||

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

+ | |||

+ | ---- | ||

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

+ | <pre> | ||

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

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