Sum of 2 = X¶

Write a program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.

Method 1: Sorting and Two-Pointers technique.¶

Time Complexity: Merge Sort or Heap Sort -> O(nlogn) Quick Sort -> O(n^2) Auxiliary Space: O(n) for merge sort and O(1) for Heap Sort.

bool hasArrayTwoCandidates(int A[], int arr_size,
                           int sum)
{
    int l, r;

    sort(A, A + arr_size);

    l = 0;
    r = arr_size - 1;
    while (l < r) {
        if (A[l] + A[r] == sum)
            return 1;
        else if (A[l] + A[r] < sum)
            l++;
        else 
            r--;
    }
    return 0;
}

Method 2: Hashing¶

Time Complexity: O(n). Auxiliary Space: O(n).

void printPairs(int arr[], int arr_size, int sum)
{
    unordered_set<int> s;
    for (int i = 0; i < arr_size; i++) 
    {
        int temp = sum - arr[i];

        if (s.find(temp) != s.end())
            cout << "Pair with given sum "
                 << sum << " is (
                           " << arr[i] << ",
                " 
                    << temp << ")" << endl;

        s.insert(arr[i]);
    }
}

Method 3: Using remainders of the elements less than x.¶

Time Complexity: O(n+x) Auxiliary Space: O(x)

void printPairs(int a[], int n, int x)
{
      int i;
    int rem[x];

    for (i = 0; i < x; i++) 
    {
        rem[i] = 0;
    }

    for (i = 0; i < n; i++) 
    {
        if (a[i] < x) 
        {
            rem[a[i] % x]++;
        }
    }

    for (i = 1; i < x / 2; i++) 
    {
        if (rem[i] > 0 && rem[x - i] > 0) 
        {
            cout << "Yes"
                 << "\n";
            break;
        }
    }

    if (i >= x / 2) 
    {
        if (x % 2 == 0) 
        {
            if (rem[x / 2] > 1) 
            {
                cout << "Yes"
                     << "\n";
            }
            else
            {
                cout << "No"
                     << "\n";
            }
        }
        else
        {
            if (rem[x / 2] > 0 && 
                  rem[x - x / 2] > 0)
            {
                cout << "Yes"
                     << "\n";
            }
            else
            {
                cout << "No"
                     << "\n";
            }
        }
    }
}