Check if pair with given Sum exists in Array (Two Sum)

You are given an array of integers and sum. You have to find out if there exist a pair of sum is equal to that sum or not. Print “Yes” if exist, else “No”.

Examples:

Input: 
1,2,2,4,4 
Sum:8
Output: Yes

Input: 
2,3,4,5 
Sum:6
Output: No

Approach-1: Brute Force method:
In this method we iterate two for loops just to check for each pair is equal to the given sum or not.
So this method in worst case, will take O(n^2) time complexity.
So this is not so efficient approach.

#include <iostream>
using namespace std;

int main()
{
    int arr[5] = {1, 2, 2, 4, 4};
    int sum = 8;
    bool found = false; // Initialize a flag 

    for (int i = 0; i < 5; i++) 
    {
        for (int j = i + 1; j < 5; j++)
        {
            if (arr[i] + arr[j] == sum)
            {
                cout << "Yes" << endl;
                found = true; // if found
                break;
            }
        }
        if (found) // if already true
            break;
    }

    if (!found) // if not true
    {
        cout << "No" << endl;
    }

    return 0;
}

Output:

Yes

Approach-2: Using sorting:

i. Sort the array.
ii. take 1st and last element of that array.

If sum is greater than given sum then take previous element of last one, if sum is less then take next element of 1st one.
This way it will iterate.
So Time complexity in this case is O(nLogn).

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int arr[5] = {1, 2, 2, 4, 4};
    int sum = 8;
    sort(arr, arr + 5);
    int f = 0, j = 4, i = 0;

    while (i < 5 && j >= 0)
    {
        if (arr[i] + arr[j] > sum)
            j--;
        else if (arr[i] + arr[j] < sum)
            i++;
        else
        {
            f = 1;
            cout << "Yes" << endl;
            break;
        }
    }

    if (f == 0)
        cout << "No" << endl;

    return 0;
}

Output:

Yes

Can we find more efficient solution?

Approach-3: Using another array:
We simply iterate for every element of the array, and store the complement of that number in another array.
For every element we check (sum-element) is exist in that array or not.
Below is the implementation.
This will take time complexity of O(n).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v;
    int sum = 8;
    int arr[5] = {1, 2, 2, 4, 4};

    for (int i = 0; i < 5; i++)
    {
        v.push_back(arr[i]);
    }

    vector<int> c;

    for (int i = 0; i < 5; i++)
    {
        if (find(c.begin(), c.end(), v[i]) != c.end())
        {
            cout << "Yes" << endl;
            return 0;
        }
        c.push_back(sum - v[i]); // complement of the element
    }

    cout << "No" << endl;
    return 0;
}

Output:

Yes

Similar Reads