cs341a1/q5/a1q5.cpp

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    string en;
    int n;
    getline(cin, en);
    stringstream cast(en);
    cast >> n; // get the length of the array we are manipulating

    int * a = (int *) malloc(n * sizeof(int));
    int * b = (int *) malloc(n * sizeof(int));
    
    for (int i = 0; i < n; ++i)
    {
        // get each line which is 2 ints, put into A and B
        string input;
        getline(cin, input);
        stringstream nums(input);
       
        nums >> a[i];
	nums >> b[i];
    }
    
    int clen = (n * (n + 1)) / 2; // total possible sums in an array of length n
    int * c = (int *) malloc(clen * sizeof(int));
    int tempcount = 0;
    
    // Store within c the possible sums inside b
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j, ++tempcount)
        {
            c[tempcount] = b[i] + b[j];
        }
    }
    
    // sort c, with time complexity n squared log (n squared), which reduces to n squared log n
    sort(c, c + clen);
    
    // for reach sum in a, see if it is in c. n squared checks of log (n squared), or n squared log n
    for (int i = 0; i < clen; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            if (binary_search(c, (c + clen), (a[i] + a[j])))
            {
                free(a); free (b); free(c);
		cout << "TRUE" << endl;
                return 0;
            }
        }
    }
    
    free(a); free(b); free(c);
    cout << "FALSE" << endl;
    return 0;
}