Pair in an Array with Given Sum
“Pair in an Array with Given Sum” is one of the favorite technical interview problems. Here, we are given an array with ‘n’ elements and a target value ‘x’. Our task is to find a pair in an array, whose sum is equal to target value ‘x’.
Example (Pair in an Array with given sum):
INPUT: Arr[] = {5, 7, 4, 9, 12} sum = 16 OUTPUT: Pair is present in array with sum as 16
There are multiple methods to find a pair in an array with given sum. Some of them are:
METHOD 1: Brute-Force Approach to find pair in an array with given sum
The steps required to find a pair in an array with given sum is as follows:
- Use two nested loops for the solution.
- For every element of the array, traverse the array to check whether any other element exist which sums up to ‘x’.
- If the pair exist, return ‘Yes’, else return ‘false’.
The time complexity of this solution is O(n^2), where ‘n’ is the size of the array.
C++ Program to find a pair in an array with given sum is as follows:
/* C++ Program to find a pair in an array with given Sum */
#include <bits/stdc++.h>
using namespace std;
void checkSum(int arr[],int n,int sum)
{
int i,j;
for(i=0;i<n;i++)
{
int temp_sum = arr[i];
for(j=0;j<n;j++)
{
// Make sure not add element with itself
if(i!=j)
{
if(temp_sum + arr[j] == sum)
{
cout<<"The Pair is Present in an Array with sum as "<<sum;
return;
}
}
}
}
cout<<"The Pair is not Present in an Array with sum as "<<sum;
}
int main()
{
int arr[5] = {1, 2, 4, 6, 8};
int sum = 12;
checkSum(arr,5,sum);
return 0;
}
OUTPUT: The Pair is Present in an Array with sum as 12
Method 2: Using Hashing to find Pair in an array with given sum
The steps required to find a pair in an array with given sum is as follows:
- Create an empty ‘set’ of preferred data type (i.e., int).
- For every element of the array, if the (x-arr[i]) exists in the set, return true.
- Else return False.
The time complexity of this solution is O(nlogn), where ‘n’ is the size of the array and ‘logn’ for inserting and searching in set.
C++ Program to find pair in an array with given sum is as follows:
/* C++ Program to find pair in an array with given Sum */
#include <bits/stdc++.h>
using namespace std;
void checkSum(int arr[],int n,int sum)
{
/* create a set*/
set<int>st;
for(int i = 0; i< n; i++)
{
/* Initialize temp with remaining of sum
after subtracting it with arr[i] */
int temp = sum - arr[i];
/* Check if temp is present in an array or not */
if(st.find(temp) != st.end())
{
cout<<"The Pair is present in the array with sum as "<<sum;
return;
}
/* If not present, insert arr[i] into set */
st.insert(arr[i]);
}
cout<<"The Pair is not present in the array with sum as "<<sum;
}
int main()
{
int arr[5] = {1, 2, 4, 6, 8};
int sum = 12;
checkSum(arr,5,sum);
return 0;
}
OUTPUT: The Pair is present in the array with sum as 12
Related Posts:
- Find Most Frequent Character of the String.
- Check Anagram Strings.
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find First Non-Repeating Character of the String.
- Find Most Frequent Element of the Array.
- Find First Repeating Element of an Array.
- Find Majority Element of an Array.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.
- Bubble Sort on Linked List.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes in a Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.
- Delete without head pointer of the Linked List.
- Delete All Occurrences of particular node of the Linked List.