# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1430760778 18000
# Node ID b06f215a4c6916f6f93a3717de274e81e48a989e
# Parent  5b53a317106cf008903db5a390eb6c216dc9307d
Added two variants of two_sum.cpp

diff -r 5b53a317106c -r b06f215a4c69 two_sum/two_sum.cpp
--- a/two_sum/two_sum.cpp	Fri May 01 16:28:22 2015 -0500
+++ b/two_sum/two_sum.cpp	Mon May 04 12:32:58 2015 -0500
@@ -15,6 +15,10 @@
 // into the hash, which adds only a small constant to the running time per
 // iteration of the loop.)
 
+// NOTE: Compare this to two_sum_hash.cpp, which implements the same algorithm
+// for arbitrary input arrays and prints all matching pairs instead of just the
+// first.
+
 // Usage: Pass the target value as a command line option, and the number array as
 // values on stdin, one item per line.
 
diff -r 5b53a317106c -r b06f215a4c69 two_sum/two_sum_hash.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/two_sum/two_sum_hash.cpp	Mon May 04 12:32:58 2015 -0500
@@ -0,0 +1,65 @@
+// 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: 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.
+
+// 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.)
+
+// Usage: Pass the target value as a command line option, and the number array as
+// values on stdin, one item per line.
+
+#include <map>
+#include <string>
+#include <cstdlib>
+#include <iostream>
+#include <vector>
+
+void two_sum( std::vector<long> vec, long target ) {
+    std::map<long, long> hash;
+
+    for ( long i=0; i < vec.size(); i++ ) {
+        hash[vec[i]] = i;
+        }
+
+    long lookfor;
+    long i = 0;
+    std::map<long, long>::iterator it;
+    while ( i < vec.size() ) {
+        if ( vec[i] <= target/2 ) {
+            lookfor = target - vec[i];
+            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).first != vec[i] ) ) {
+                std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;
+                }
+            }
+        i++;
+        }
+    }
+
+int main( int argc, char **argv ) {
+    char *endptr = NULL;
+    long target = strtol( argv[1], &endptr, 10);
+
+    std::vector<long> vec;
+    long num;
+    std::string s;
+
+    while ( std::cin >> s ) {
+        num = strtol( s.c_str(), &endptr, 10);
+        vec.push_back(num);
+        }
+
+    two_sum( vec, target );
+
+    exit(EXIT_SUCCESS);
+    }
+
+
diff -r 5b53a317106c -r b06f215a4c69 two_sum/two_sum_sort.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/two_sum/two_sum_sort.cpp	Mon May 04 12:32:58 2015 -0500
@@ -0,0 +1,65 @@
+// 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.
+
+// 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.
+// Space complexity if O(1), though, since no extra space is needed for the operations.
+
+// Usage: Pass the target value as a command line option, and the number array as
+// values on stdin, one item per line.
+
+#include <algorithm>
+#include <vector>
+#include <string>
+#include <cstdlib>
+#include <iostream>
+
+long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
+    while ( max >= min ) {
+        long mid = min + (max - min) / 2;
+        if ( vec[mid] == lookfor )
+            return mid;
+        else if ( vec[mid] > lookfor )
+            max = mid - 1;
+        else
+            min = mid + 1;
+        }
+    return -1;
+    }
+
+void two_sum( std::vector<long> vec, long target ) {
+    std::sort( vec.begin(), vec.end() );
+
+    long lookfor;
+    long i = 0;
+    while ( vec[i] <= target/2 ) {
+        lookfor = target - vec[i];
+        long pos = binary_search( vec, lookfor, 0, vec.size()-1 );
+        if ( pos != -1 && pos != i ) {
+            std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << pos << ")" << std::endl;
+            }
+        i++;
+        }
+    }
+
+int main( int argc, char **argv ) {
+    char *endptr = NULL;
+    long target = strtol( argv[1], &endptr, 10);
+
+    std::vector<long> vec;
+    long num;
+    std::string s;
+
+    while ( std::cin >> s ) {
+        num = strtol( s.c_str(), &endptr, 10);
+        vec.push_back(num);
+        }
+
+    two_sum( vec, target );
+
+    exit(EXIT_SUCCESS);
+    }
+
+