Given an array arr[] of n numbers and another number target, the task is to check whether or not there exist two elements in arr[] whose sum is exactly the target. That means you just need to find whether or not there exist two elements in an array whose sum is exactly equal to the target.
Let’s consider a few examples to understand the problem.
Example 1:
Input: arr = [4,8,11,15], target = 12 Output: Yes Explanation: If we calculate the sum of the output,4 + (8) = 12
Example 2:
Input: arr = [-2,8,1,15], target = -1 Output: Yes Explanation: If we calculate the sum of the output, (-2) + 1 = -1
Brute Force Approach:
This is a basic approach to solve this problem but it is not recommended to use.
- Execute the two nested loops to check every possible pair of numbers in the given array to see whether the sum is equal to the target number or not.
- The outer loop iterates through the elements of the array using enumerate. The outer loop variable i represents the index, and arr[i] represents the element at that index.
- The inner loop starts from the i+1 index. This ensures that you don’t use the same combination twice. The inner loop variable j represents the index, and arr[j] represents the element at that index.
- If the sum of (arr[i] + arr[j]) is equal to the target returns “YES” otherwise returns “NO”.
C Code:
/*
* This C program check if pair with given
Sum exists in Array (Two Sum) or not
*/
#include <stdio.h>
// Function to find and print pair
int chkPairSum(int arr[], int size, int target)
{
int i, j;
int isFound = 0;
for (i = 0; ((i< size) && (!isFound)); ++i)
{
for (j = (i + 1); j < size; ++j)
{
if (arr[i] + arr[j] == target)
{
isFound = 1;
}
}
}
return isFound;
}
int main()
{
int arr[] = {-2,8,1,15};
int target = -1;
int size = sizeof(arr) / sizeof(arr[0]);
const int foundPairSum = chkPairSum(arr, size, target);
if (foundPairSum)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}
Output: YES Worst Time Complexity: O(N2), where N = size of the array. Space Complexity: O(1) as we are not using any extra space.
C++ Code:
/*
* This C++ program check if pair with given
Sum exists in Array (Two Sum) or not
*/
#include <bits/stdc++.h>
using namespace std;
bool chkPairSum(vector<int>& arr, int target)
{
bool isFound = false;
for(unsigned int i = 0; ((i< arr.size()) && (!isFound)); ++i)
{
for(unsigned int j = (i+1) ; j< arr.size(); ++j)
{
if(target == (arr.at(i)+ arr.at(j)))
{
isFound = true;
}
}
}
return isFound;
}
int main()
{
vector<int> arr {-2,8,1,15};
int target = -1;
const bool foundPairSum = chkPairSum(arr,target);
if (foundPairSum)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}
Using Two-Pointer technique:
Using the two-pointer technique you can also solve the above problem but before using the pointers approach you have to sort the array first.
Now let’s see the approach to how the two-pointer technique works.
First take the two pointers, one representing the first element and the second representing the last element of the array.
Now add the values kept at both pointers. If their sum is smaller than the target then we shift the left pointer to the right otherwise we shift the right pointer to the left, in order to get closer to the sum. You need to do the same steps until you get the sum that is equal to the target.
C Code:
/* C program to check if given array
has 2 elements whose sum is equal
to the given value
*/
#include <stdio.h>
//function to swap variable
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
/* partition function takes last element as pivot and places
the pivot element at its correct position. It means all
smaller element will be placed to left all greater elements
to right of pivot
*/
int partition (int arr[], int start, int end)
{
int pivot = arr[end]; // pivot
int i = (start - 1);
int j = start;
for (j = start; j <= (end - 1); j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[end]);
return (i + 1);
}
/*
arr[] --> Array to be sorted,
start --> Starting index,
end --> Ending index */
void quickSort(int arr[], int start, int end)
{
if (start < end)
{
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(arr, start, end);
// recursive call on the left of pivot
quickSort(arr, start, pi - 1);
// recursive call on the right of pivot
quickSort(arr, pi + 1, end);
}
}
/*To check pair is exist or not whose sum equal to
target.
*/
int chkTwoSum(int arr[], int arr_size, int sum)
{
int isPairFound = 0;
//Sort the elements
quickSort(arr, 0, arr_size - 1);
// Now you have sorted array
// represents first pointer
int l = 0;
// represents second pointer
int r = (arr_size - 1);
while (l < r)
{
if (arr[l] + arr[r] == sum)
{
isPairFound = 1;
break;
}
else if (arr[l] + arr[r] < sum)
{
l++;
}
else // arr[i] + arr[j] > sum
{
r--;
}
}
return isPairFound;
}
int main()
{
int arr[] = {-2,8,1,15};
int target = -1;
int arr_size = sizeof(arr) / sizeof(arr[0]);
const int foundPairSum = chkTwoSum(arr, arr_size, target);
if (foundPairSum)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}
C++ Code:
/*
* This C++ program check if pair with given
Sum exists in Array (Two Sum) or not
*/
#include <bits/stdc++.h>
using namespace std;
/*To check pair is exist or not whose sum equal to
target.
*/
bool chkTwoSum(vector<int>& arr, int target)
{
//create tmp vector
vector<int> tmp(arr);
bool isFound = false;
//Sort the array first
sort(tmp.begin(), tmp.end());
// represents first pointer
int l = 0;
// represents second pointer
int r = tmp.size() - 1;
while (l < r)
{
// If we find a pair
if (tmp.at(l) + tmp.at(r) == target)
{
isFound = true;
break;
}
/*If sum of elements at current
pointers is less, we move towards
higher values by doing l++
*/
else if (tmp.at(l) + tmp.at(r) < target)
{
l++;
}
/* If sum of elements at current
pointers is more, we move towards
lower values by doing r--.
*/
else
{
r--;
}
}
return isFound;
}
int main()
{
vector<int> arr {-2,8,1,0,15};
int target = -1;
const bool foundPairSum = chkTwoSum(arr,target);
if (foundPairSum)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}
Using map:
Using the map you can solve the problem in an optimized way.
Approach:
- Create an unordered map.
- Given target is made up of the sum of two array elements, arr[i], and another element which is (target – arr[i]).
- Now you need to iterate through the array.
- If (target – arr[i]) is not there in the map, you need to add arr[i] and its index in the map.
- If (target – arr[i]) exists in the map, you need to return true to indicate that the array has a pair of two numbers that sum equal to the given target number.
C++ Code:
/*
* This C++ program check if pair with given
Sum exists in Array (Two Sum) or not using the map
*/
#include <bits/stdc++.h>
using namespace std;
/*To check pair is exist or not whose sum equal to
target.
*/
bool chkTwoSum(vector<int>& arr, int target)
{
unordered_map<int,int> m;
bool isFound = false;
for(unsigned int i = 0; i < arr.size(); ++i)
{
int counterPart = (target - arr[i]);
if(m.find(counterPart) == m.end())
{
m[arr[i]] = i;
}
else
{
isFound = true;
break;
}
}
return isFound;
}
int main()
{
vector<int> arr {-2,8,1,0,15};
int target = -1;
const bool foundPairSum = chkTwoSum(arr,target);
if (foundPairSum)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}
Output: YES Time complexity: O(N) Space complexity: O(N)