Difference between revisions of "TADM2E 4.8"

Revision as of 21:24, 4 February 2016

(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 (S[i],S[j]);
    break;
  }
}

"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.