Given a file name of a file containing an array of unsorted integers A and integer N, find all pairs of numbers within A which add up to N.

find_sum_pairs.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>

using namespace std;




/// Given an integer N and an array of unsorted integers A
/// find all pairs of numbers within A which add up to N.
int main(int argc, char* argv[])
{

  // get the arguments
  if (argc != 3)
  {
    cerr << "expected anagram integer_list_filename desired_sum" << endl;
    return -1;
  }

  string filename = argv[1];
  int desired_sum = atoi(argv[2]);


  // read the file
  ifstream list_file(filename.c_str(), std::ifstream::in);

  vector<int> int_vector;
  int value;
  while(list_file >> value)
  {
    int_vector.push_back(value);
  }


  // sort in approx O(n log n)
  sort(int_vector.begin(), int_vector.end());


  // find the pairs
  vector< pair<int, int> > result;

  size_t left_i = 0;
  const size_t left_end = int_vector.size();

  while ((left_i != left_end) && (int_vector[left_i] < desired_sum))
  {
    const int l = int_vector[left_i];
    
    size_t right_i = int_vector.size() - 1;
    while (left_i != right_i)
    {

      const int r = int_vector[right_i];

      if (desired_sum == (l + r))
      {
        result.push_back(pair<int, int>(l, r));
      }
      --right_i;
    }

    ++left_i;
  }


  // print the results
  for (vector< pair<int, int> >::iterator i = result.begin(); i != result.end(); ++i)
  {
    cout << i->first << " " << i->second << endl;
  }

  return 0;
}