# Difference between revisions of "TADM2E 4.8"

From Algorithm Wiki

(Recovering wiki) |
m (Removed the extra break) |
||

(One intermediate revision by one other user not shown) | |||

Line 33: | Line 33: | ||

for (i = 0; i < j; i++) | for (i = 0; i < j; i++) | ||

{ | { | ||

− | while( (i < j) && (S[j] + S[i] > x ) | + | while( (i < j) && (S[j] + S[i] > x ) ) |

{ j--; | { j--; | ||

} | } | ||

− | if (x == (S[j] + S[i]) | + | if (x == (S[j] + S[i]) ) |

{ | { | ||

− | return | + | return true; |

− | + | ||

} | } | ||

} | } | ||

Line 45: | Line 45: | ||

"i" scans from left to right, "j" from right to left, | "i" scans from left to right, "j" from right to left, | ||

looking for the right pair... | looking for the right pair... | ||

+ | </pre> | ||

+ | |||

+ | Yet another solution to solve both parts in linear time using a hashtable. | ||

+ | <pre> | ||

+ | Initialize a hash-table backed dictionary D; // O(n*lg(n)) if the underlying structure is a BST. | ||

+ | for each e in S: | ||

+ | delta = x - e; | ||

+ | if Search(D, delta) is not NULL: | ||

+ | return (e, delta); | ||

+ | else | ||

+ | Insert(D, {e => delta}); // Insert a record with key e and value delta. | ||

</pre> | </pre> |

## Latest revision as of 00:45, 22 March 2017

(a):

Sort S with any nlogn sorting method of your choice. for( int i = 1; i <= n; ++i ) { int j = x - S[i]; Binary search for j in the sub-array of S[i+1~n] and close the problem once it's been found; }

(b):

Subtract each of S[1~n] from x to get a new array of real numbers T[1~n]. int i = 1, j = 1; while( i <=n && j <= n ) { if( S[i] == T[j] ) { problem solved; break; } else { S[i] < T[j] ? ++i : ++j; } }

Another Solution to part B without creating the additional Array..

i = 0; j = n - 1; for (i = 0; i < j; i++) { while( (i < j) && (S[j] + S[i] > x ) ) { j--; } if (x == (S[j] + S[i]) ) { return true; } } "i" scans from left to right, "j" from right to left, looking for the right pair...

Yet another solution to solve both parts in linear time using a hashtable.

Initialize a hash-table backed dictionary D; // O(n*lg(n)) if the underlying structure is a BST. for each e in S: delta = x - e; if Search(D, delta) is not NULL: return (e, delta); else Insert(D, {e => delta}); // Insert a record with key e and value delta.