cs341a1/q5/q5.cpp

#include <iostream>
#include <cstdlib>
#include <string>

/*int n;
int twon = 2 * n;
int * a;
int * b;
int * sums = malloc(2 * sizeof(b));
int pos = 0;

for (int i = 0; i < twon; i++)
{
    for (int j = (i + 1); j < twon; j++, pos++)
    {
        sums[pos] = b[i] + b[j];
    }
}

sort c;

for (int i = 0; i < twon; i++)
{
    for (int j = (i + 1); j < twon; j++, pos++)
    {
        if sums.search(a[i] + a[j]) return true;
    }
}

return false;

================*/

int n;
std::cin >> n; // get the length of the array we are manipulating

int * a = malloc(n * sizeof(int));
int * b = malloc(n * sizeof(int));

for (int i = 0; i < n; ++i)
{
    // get each line which is 2 ints, put into A and B
    std::string input;
    std::getline(std::cin, input);
    std::stringstream nums(input);
    
    nums >> a[i];
    nums >> b[i];
}

/*
int clen = 2 * n;
int * C = malloc(clen * sizeof(int)); // to hold the list of possible sums
int tempcount = 0;

for (int i = 0; i < n; i++)
{
    for (int j = (i + 1); j < n; ++j, ++tempcount)
    {
        C[tempcount] = (B[i] + B[j]);
        C[clen - tempcount - 1] = (A[i] + A[j]);
    }
} // n squared

sort(C, C + clen); // n^2 log n squared == n^2 log n */

int clen = (n * (n - 1)) / 2; // total possible sums in an array of length n
int * c = 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 + 1); 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
std::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 + 1); j < n; ++j)
    {
        if (std::binary_search(c, c + clen), (a[i] + a[j]))
        {
            free(a); free (b); free(c);
            cout << 1 << endl;
            return true;
        }
    }
}

free(a); free(b); free(c);
cout << 0 << endl;
return false;