2-SUM algorithm using a sorted vector

Question

I'm trying to implement a variant of the 2-SUM algorithm using a sorted vector in C++. The task is to read in a file containing 10^6 integers and compute the number of distinct integers (x and y) that sum to t, where t is in the interval [-10000, 10000]. I've tested my code on a few test cases and it seems to be working, but I'm not getting the correct answer for the programming assignment. This is for a Coursera Algorithms: Design and Analysis course. So, no official credit will be received for this assignment. I'd appreciate any help. You can find my code below.

/*
 * TwoSums.cpp
 * Created on: 2013-08-05
 * 
 * Description: Implemented a variant of the 2-SUM algorithm for sums between -10000 and 10000.
 * The task was to compute the number of target values t in the interval [-10000,10000]
 * (inclusive) such that there are distinct numbers x,y in the input file (./HashInt.txt)
 * that satisfy x+y=t. The input file was taken from the Algorithms: Design and Analysis course
 * taught by Tim Roughgarden on Coursera.
 * 
 */

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <set>

#define LOWER -10000
#define HIGHER 10000

using namespace std;

const char* inputfile = "./HashInt.txt";

/*
 * Precondition: The inputfile is a file that contains integers, both 
 *               positive and negative. Each line contains an integer.
 * 
 * Postcondition: Every number in the file will be stored in vector V. 
 */

int ReadFile(vector<long>& V) {
    std::string line;
    std::ifstream infile;
    infile.open(inputfile);

    if(infile.fail())
    {
        cout << "Problem opening file.";
        return -1;
    }

    while (getline(infile, line)) {
        istringstream iss(line);
        long a;
        iss >> a;
        V.push_back(a);
    }

    return 0;
}

/*
 * Precondition: V is a sorted vector of integers
 * 
 * Postcondition: The number of target values (t) in the interval
 * [-10000,10000] will be displayed in stdout such that there
 * are distinct numbers x,y in the input file that satisfy x+y=t.
 */

void TwoSum (const vector<long>& V) {
    vector<long>::iterator x;
    vector<long>::iterator y;
    unsigned long count = 0;

    for (int i = LOWER; i <= HIGHER; ++i) {
        x = V.begin();
        y = V.end()-1;

        while (x != y) {
            long sum = *x + *y;
            if (sum == i) {
                count++;
                break;
            }

            else if(sum < i) {
                x+=1;
            }

            else {
                y-=1;
            }
        }
    }
    cout << "Count is: " << count << endl;
}

int main () {

    // Read integers, store in vector
    vector<long>V;
    if (ReadFile(V) < 0) return -1;

    // Erase duplicate numbers and sort vector
    set<long> s;
    unsigned long size = V.size();
    for( unsigned long i = 0; i < size; ++i ) s.insert( V[i] );
    V.assign(s.begin(),s.end() );

    // Implement 2-SUM algorithm for numbers between -10000 and 10000
    TwoSum(V);

    return 0;
}

Possible duplicate of [Linear time algorithm for 2-SUM](http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum) — Leonid Volnitsky, Aug 06 '13 at 09:02

score 0 · Answer 1 · answered Aug 06 '13 at 11:22

This program does not ask the user for input to use as the value of 't'. So I'm assuming you do not want the number of x-y pairs that add up to a specific t. Your program goes through every possible value for 't' and sees if there is an x-y pair that adds up to that, and then moves on to the next value for 't'.

score 0 · Answer 2 · answered Aug 21 '15 at 18:36

0

I believe you need to sort the vector of data before going for loop through LOWER to HIGHER. Because, data must be sorted to apply the algorithm that you have implemented with x and y as two iterators in opposite directions.

answered Aug 21 '15 at 18:36

shreyans800755

244
1
10

2-SUM algorithm using a sorted vector

2 Answers2