# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1430770826 18000
# Node ID d48b3fb142f078a4ad2b275defe4e6e7de1afe49
# Parent  b06f215a4c6916f6f93a3717de274e81e48a989e
Updated comments.  Correct subtle logic error in two_sum_hash.cpp that would have  resulted in bad output when there are repeated values in the input.

diff -r b06f215a4c69 -r d48b3fb142f0 two_sum/two_sum_hash.cpp
--- a/two_sum/two_sum_hash.cpp	Mon May 04 12:32:58 2015 -0500
+++ b/two_sum/two_sum_hash.cpp	Mon May 04 15:20:26 2015 -0500
@@ -4,23 +4,23 @@
 // Solution: Add the input numbers to a hash with the number as the hash key,
 // and it's index position in the input as the hash value.
 
-// At each step we can do an O(1) lookup in the hash to see if target - num has
-// already been added to the hash.  If it has, we terminate processing and print
-// the two numbers (along with their indices).  Otherwise we add num to the hash
-// and loop back to read the next input number.
+// For each value in the array, check to see if (target - value) is also in the
+// hash and if so print the pair of nubmers.  We need not consider values
+// greater than target/2 since this would generate a duplicate pair when we
+// eventually come across (target - value) itself in the array.
 
-// Overall performance is O(N) in the worst case, since in that case we must
-// process each input item exactly once.  (For each item, we perform one lookup
-// into the hash, which adds only a small constant to the running time per
-// iteration of the loop.)
+// We are using an extra O(N) amount of memory for the hash table, but doing so
+// gives us O(1) lookup time to see if (target - value) is also in the array, so
+// once the hash is built in O(N) time we need only another O(N) amount of time
+// to find all pairs, yielding an overall O(N) running time.
 
 // Usage: Pass the target value as a command line option, and the number array as
 // values on stdin, one item per line.
 
+#include <cstdlib>
+#include <iostream>
 #include <map>
 #include <string>
-#include <cstdlib>
-#include <iostream>
 #include <vector>
 
 void two_sum( std::vector<long> vec, long target ) {
@@ -36,7 +36,7 @@
     while ( i < vec.size() ) {
         if ( vec[i] <= target/2 ) {
             lookfor = target - vec[i];
-            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).first != vec[i] ) ) {
+            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).second != i ) ) {
                 std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;
                 }
             }
diff -r b06f215a4c69 -r d48b3fb142f0 two_sum/two_sum_sort.cpp
--- a/two_sum/two_sum_sort.cpp	Mon May 04 12:32:58 2015 -0500
+++ b/two_sum/two_sum_sort.cpp	Mon May 04 15:20:26 2015 -0500
@@ -1,7 +1,10 @@
 // Problem: given an input array of numbers, and a target value, find all pairs
 // of numbers in the input which sum to the target value.
 
-// Solution: Sort the input data.  We can now use binary search to look up target numbers.
+// Solution: Sort the input data.  For each value in the array, use binary
+// search to see if (target - value) is also in the array, and if so print the
+// pair of numbers.  We need not consider values greater that target/2 since 
+// the the data is sorted, and (target - value) would have already been checked.
 
 // Time performance is O(N log N) for the lookup, and varies for the sort,
 // though here it is also O(N log N) giving O(N log N) overall performance.
@@ -11,10 +14,10 @@
 // values on stdin, one item per line.
 
 #include <algorithm>
-#include <vector>
-#include <string>
 #include <cstdlib>
 #include <iostream>
+#include <string>
+#include <vector>
 
 long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
     while ( max >= min ) {