TADM2E 4.8 - Revision history

Praneel: Removed the extra break

2017-03-22T00:45:04Z

Removed the extra break

Ysag: Yet another solution in linear time, using a hashtable.

2016-02-04T21:24:21Z

Yet another solution in linear time, using a hashtable.

Algowikiadmin: Recovering wiki

2014-09-11T18:23:43Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:06Z

Recovering wiki

New page

(a):
<pre>
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;
}
</pre>
(b):
<pre>
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;
}
}
</pre>

Another Solution to part B without creating the additional Array..
<pre>
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...
</pre>

@@ Line 33: / Line 33: @@
 for (i = 0; i < j; i++)
+{
-   while( (i < j) && (S[j] + S[i] > x )
+   while( (i < j) && (S[j] + S[i] > x ) )
    { j--;
+   }
-   if (x == (S[j] + S[i])
+   if (x == (S[j] + S[i]) )
+   {
-     return (S[i],S[j]);
+     return true;
-    break;
+   }
+}

@@ Line 45: / Line 45: @@
 "i" scans from left to right, "j" from right to left,
 looking for the right pair...
 </pre>

@@ Line 1: / Line 1: @@
 (a):
-&lt;pre&gt;
+<pre>
 Sort S with any nlogn sorting method of your choice.
-for( int i = 1; i &lt;= n; ++i )
+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;
+}
-&lt;/pre&gt;
+</pre>
 (b):
-&lt;pre&gt;
+<pre>
 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 &lt;=n &amp;&amp; j &lt;= n )
+while( i <=n && j <= n )
+{
      if( S[i] == T[j] )
@@ Line 21: / Line 21: @@
      else
+     {
-         S[i] &lt; T[j] ? ++i : ++j;
+         S[i] < T[j] ? ++i : ++j;
+     }
+}
-&lt;/pre&gt;
+</pre>
 Another Solution to part B without creating the additional Array..
-&lt;pre&gt;
+<pre>
 i = 0;
 j = n - 1;
-for (i = 0; i &lt; j; i++)
+for (i = 0; i < j; i++)
+{
-   while( (i &lt; j) &amp;&amp; (S[j] + S[i] &gt; x )
+   while( (i < j) && (S[j] + S[i] > x )
    { j--;
+   }
@@ Line 43: / Line 43: @@
+}
-&quot;i&quot; scans from left to right, &quot;j&quot; from right to left,
+"i" scans from left to right, "j" from right to left,
 looking for the right pair...
-&lt;/pre&gt;
+</pre>