Given an array A[] and a number x, check for pair in A[] with sum as x

CODE

Given an array A[] and a number x, check for pair in A[] with sum as 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 (Use Sorting)

// C++ program to check if given array

// has 2 elements whose sum is equal

// to the given value

#include <bits/stdc++.h>

using namespace std;

// Function to check if array has 2 elements

// whose sum is equal to the given value

bool hasArrayTwoCandidates(int A[], int arr_size, int sum)

{

    int l, r;

    /* Sort the elements */

    sort(A, A + arr_size);

    /* Now look for the two candidates in

       the sorted array*/

    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 // A[i] + A[j] > sum

            r--;

    }

    return 0;

}

/* Driver program to test above function */

int main()

{

    int A[] = {1, 4, 45, 6, 10, -8};

    int n = 16;

    int arr_size = sizeof(A) / sizeof(A[0]);

    // Function calling

    if(hasArrayTwoCandidates(A, arr_size, n))

        cout << "Array has two elements with given sum";

    else

        cout << "Array doesn't have two elements with given sum";

return 0;

}

Output :

Array has two elements with the given sum

METHOD 2 (Use Hashing)

// C++ program to check if given array

// has 2 elements whose sum is equal

// to the given value

#include <bits/stdc++.h>

using namespace std;

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 (temp >= 0 && s.find(temp) != s.end())

            cout << "Pair with given sum " << sum <<  " is (" << arr[i] << ", " << temp << ")" << endl;

        s.insert(arr[i]);

    }

}

/* Driver program to test above function */

int main()

{

    int A[] = {1, 4, 45, 6, 10, 8};

    int n = 16;

    int arr_size = sizeof(A)/sizeof(A[0]);

    // Function calling

    printPairs(A, arr_size, n);

    return 0;

}

Output:

Pair with given sum 16 is (10, 6)