Find Pair With Given Sum

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

Example 1:

Input:  arr[]={10,15,3,7}, k=17
Output: true

Example 2:

Input:  arr[]={10,5,3,7}, k=4
Output: false

Approach 1: Using two for loops

C++

#include <bits/stdc++.h>
using namespace std;

bool isPairSum(vector<int> arr, int k)
{
    //find the size of array
    int n = arr.size();

    //check for every pair
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            //if sum is same as k then
            //return true
            if (arr[i] + arr[j] == k)
            {
                return true;
            }
        }
    }

    //if no pair then return false
    return false;
}
int main()
{
    vector<int> arr = {10, 15, 3, 7};

    int k = 17;

    if (isPairSum(arr, k))
    {
        cout << "true";
    }
    else
    {
        cout << "false";
    }

    return 0;
}

//Time Complexity: O(n^2)
//Space Complexity: O(1)

Approach 2: Using sorting

C++

#include <bits/stdc++.h>
using namespace std;

bool isPairSum(vector<int> arr, int k)
{
    //find the size of array
    int n = arr.size();

    //sort the array
    sort(arr.begin(), arr.end());

    int low = 0, high = n - 1;
    while (low < high)
    {
        //if pair with sum k is found then
        //return true
        if (arr[low] + arr[high] == k)
        {
            return true;
        }
        else if (arr[low] + arr[high] > k)
        {
            high--;
        }
        else
        {
            low++;
        }
    }

    //if no pair then return false
    return false;
}
int main()
{
    vector<int> arr = {10, 15, 3, 7};

    int k = 17;

    if (isPairSum(arr, k))
    {
        cout << "true";
    }
    else
    {
        cout << "false";
    }

    return 0;
}

//Time Complexity: O(nlogn)

Approach 3: Using memory

C++

#include <bits/stdc++.h>
using namespace std;

bool isPairSum(vector<int> arr, int k)
{
    //find the size of array
    int n = arr.size();

    set<int> st;
    for (int i = 0; i < n; i++)
    {
        int diff = k - arr[i];
        
        //if pair with sum k is found then
        //return true
        if (st.find(diff) != st.end())
        {
            return true;
        }

        //insert the current element into
        //the set
        st.insert(arr[i]);
    }
    //if no pair then return false
    return false;
}
int main()
{
    vector<int> arr = {10, 15, 3, 7};

    int k = 17;

    if (isPairSum(arr, k))
    {
        cout << "true";
    }
    else
    {
        cout << "false";
    }

    return 0;
}

//Time Complexity: O(n)
//Space Complexity: O(n)