## 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 A[] whose sum is exactly x.

**Examples:**

Input:arr[] = {0, -1, 2, -3, 1} sum = -2Output:-3, 1 Valid pair exixts. If we calculate the sum of the output, 1 + (-3) = -2Input:arr[] = {1, -2, 1, 0, 5} sum = 0Output:No valid pair exists.

**Method:** Using simple logic by calculating array’s elements itself.

`/*` ` ` `* This C++ program tells if there exists a pair in array whose sum results in x.` ` ` `*/` `#include <iostream>` `using` `namespace` `std;` `// Function to find and print pair` `bool` `chkPair(` `int` `A[], ` `int` `size, ` `int` `x) {` ` ` `for` `(` `int` `i = 0; i < (size - 1); i++) {` ` ` `for` `(` `int` `j = (i + 1); j < size; j++) {` ` ` `if` `(A[i] + A[j] == x) {` ` ` `cout << ` `"Pair with a given sum "` `<< x << ` `" is ("` `<< A[i] << ` `", "` `<< A[j] << ` `")"` ` ` `<< endl;` ` ` `return` `1;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `0;` `}` `int` `main(` `void` `) {` ` ` `int` `A[] = {0, -1, 2, -3, 1};` ` ` `int` `x = -2;` ` ` `int` `size = ` `sizeof` `(A) / ` `sizeof` `(A[0]);` ` ` `if` `(chkPair(A, size, x)) {` ` ` `cout << ` `"Valid pair exists"` `<< endl;` ` ` `}` ` ` `else` `{` ` ` `cout << ` `"No valid pair exists for "` `<< x << endl;` ` ` `}` ` ` `return` `0;` `}` `// This code is contributed by Manish Kumar (mkumar2789)` |

**Output**

Pair with a given sum -2 is (-3, 1) Valid pair exists

`/*` ` ` `* This C program tells if there exists a pair in array whose sum results in x.` ` ` `*/` `#include <stdio.h>` `// Function to find and print pair` `int` `chkPair(` `int` `A[], ` `int` `size, ` `int` `x) {` ` ` `for` `(` `int` `i = 0; i < (size - 1); i++) {` ` ` `for` `(` `int` `j = (i + 1); j < size; j++) {` ` ` `if` `(A[i] + A[j] == x) {` ` ` `printf` `(` `"Pair with a given sum %d is (%d, %d)\n"` `, x, A[i], A[j]);` ` ` `return` `1;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `0;` `}` `int` `main(` `void` `) {` ` ` `int` `A[] = {0, -1, 2, -3, 1};` ` ` `int` `x = -2;` ` ` `int` `size = ` `sizeof` `(A) / ` `sizeof` `(A[0]);` ` ` `if` `(chkPair(A, size, x)) {` ` ` `printf` `(` `"Valid pair exists\n"` `);` ` ` `}` ` ` `else` `{` ` ` `printf` `(` `"No valid pair exists for %d\n"` `, x);` ` ` `}` ` ` `return` `0;` `}` `// This code is contributed by Manish Kumar (mkumar2789)` |

**Output**

Pair with a given sum -2 is (-3, 1) Valid pair exists

** Method 1:** Sorting and Two-Pointers technique.

**Approach:** A tricky approach to solve this problem can be to use the two-pointer technique. But for using two pointer technique, the array must be sorted. Once the array is sorted the two pointers can be taken which mark the beginning and end of the array respectively. If the sum is **greater** than the sum of those two elements, shift the right pointer to decrease the value of required sum and if the sum is **lesser** than the required value, shift the left pointer to increase the value of the required sum. Let’s understand this using an example.

Let an array be {1, 4, 45, 6, 10, -8} and sum to find be 16

After sorting the array

A = {-8, 1, 4, 6, 10, 45}

Now, increment ‘l’ when the sum of the pair is less than the required sum and decrement ‘r’ when the sum of the pair is more than the required sum.

This is because when the sum is less than the required sum then to get the number which could increase the sum of pair, start moving from left to right(also sort the array) thus “l++” and vice versa.

Initialize l = 0, r = 5

A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 4

A[l] + A[r] ( -8 + 10) increment l. Now l = 1

A[l] + A[r] ( 1 + 10) increment l. Now l = 2

A[l] + A[r] ( 4 + 10) increment l. Now l = 3

A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

**Note:** If there is more than one pair having the given sum then this algorithm reports only one. Can be easily extended for this though.

**Algorithm:**

- hasArrayTwoCandidates (A[], ar_size, sum)
- Sort the array in non-decreasing order.
- Initialize two index variables to find the candidate

elements in the sorted array.- Initialize first to the leftmost index: l = 0
- Initialize second the rightmost index: r = ar_size-1

- Loop while l < r.
- If (A[l] + A[r] == sum) then return 1
- Else if( A[l] + A[r] < sum ) then l++
- Else r–

- No candidates in the whole array – return 0

`// 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 given sum

**Output:**

Array has two elements with the given sum

**Complexity Analysis:**

**Time Complexity:**Depends on what sorting algorithm we use.- If Merge Sort or Heap Sort is used then (-)(nlogn) in the worst case.
- If Quick Sort is used then O(n^2) in the worst case.

**Auxiliary Space:**This too depends on sorting algorithm. The auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

** Method 2:** Hashing.

**Approach:** This problem can be solved efficiently by using the technique of hashing. Use a **hash_map** to check for the current array value **x(let)**, if there exists a value **target_sum-x** which on adding to the former gives **target_sum**. This can be done in constant time. Let’s look at the following example.

arr[] = {0, -1, 2, -3, 1}

sum = -2

Now start traversing:

Step 1: For ‘0’ there is no valid number ‘-2’ so store ‘0’ in hash_map.

Step 2: For ‘-1’ there is no valid number ‘-1’ so store ‘-1’ in hash_map.

Step 3: For ‘2’ there is no valid number ‘-4’ so store ‘2’ in hash_map.

Step 4: For ‘-3’ there is no valid number ‘1’ so store ‘-3’ in hash_map.

Step 5: For ‘1’ there is a valid number ‘-3’ so answer is 1, -3

**Algorithm:**

- Initialize an empty hash table s.
- Do following for each element A[i] in A[]
- If s[x – A[i]] is set then print the pair (A[i], x – A[i])
- Insert A[i] into s.

**Pseudo Code :**

unordered_set s for(i=0 to end) if(s.find(target_sum - arr[i]) == s.end) insert(arr[i] into s) else print arr[i], target-arr[i]

`// 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` `(s.find(temp) != s.end())` ` ` `cout << ` `"Pair with given sum "` ` ` `<< sum << ` `" is ("` `<< arr[i] << ` `","` ` ` `<< temp << ` `")"` `<< endl;` ` ` `s.insert(arr[i]);` ` ` `}` `}` `/* Driver Code */` `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)

**Output:**

Pair with given sum 16 is (10, 6)

**Complexity Analysis:**

**Time Complexity:**O(n).

As the whole array is needed to be traversed only once.**Auxiliary Space:**O(n).

A hash map has been used to store array elements.

**Note:** If the range of numbers includes negative numbers then also it will work fine.

** Method 3:** Using remainders of the elements less than x.

**Approach:**

The idea is to count the elements with remainders when divided by x, i.e **0 to x-1**, each remainder separately. Suppose we have **x as 6**, then the numbers which are less than 6 and have remainders which add up to 6 gives sum as 6 when added. For example, we have elements, 2,4 in the array and 2%6 = 2 and 4%6 =4, and these remainders add up to give 6. Like that we have to check for pairs with remainders (1,5),(2,4),(3,3). if we have one or more elements with remainder 1 and one or more elements with remainder 5, then surely we get a sum as 6. Here we do not consider (0,6) as the elements for the resultant pair should be less than 6. when it comes to (3,3) we have to check if we have two elements with remainder 3, then we can say that “There exists a pair whose sum is x”.

**Algorithm:**

1. Create an array with size x.

2. Initialize all rem elements to zero.

3. Traverse the given array

- Do the following if arr[i] is less than x:
- r=arr[i]%x which is done to get the remainder.
- rem[r]=rem[r]+1 i.e. increasing the count of elements that have remainder r when divided with x.

4. Now, traverse the rem array from 1 to x/2.

- If(rem[i]> 0 and rem[x-i]>0) then print “YES” and come out of the loop. This means that we have a pair that results in x upon doing.

5. Now when we reach at x/2 in the above loop

- If x is even, for getting a pair we should have two elements with remainder x/2.
- If rem[x/2]>1 then print “YES” else print “NO”

- If it is not satisfied that is x is odd, it will have a separate pair with x-x/2.
- If rem[x/2]>1 and rem[x-x/2]>1 , then print “Yes” else, print”No”;

**Implementation of the** **above algorithm:**

`// Code in cpp to tell if there` `// exists a pair in array whose` `// sum results in x.` `#include <iostream>` `using` `namespace` `std;` `// Function to print pairs` `void` `printPairs(` `int` `a[], ` `int` `n, ` `int` `x)` `{` ` ` `int` `i;` ` ` `int` `rem[x];` ` ` `for` `(i = 0; i < x; i++)` ` ` `{` ` ` ` ` `// initializing the rem` ` ` `// values with 0's.` ` ` `rem[i] = 0;` ` ` `}` ` ` `for` `(i = 0; i < n; i++)` ` ` `{` ` ` `if` `(a[i] < x)` ` ` `{` ` ` `// Perform the remainder` ` ` `// operation only if the` ` ` `// element is x, as numbers` ` ` `// greater than x can't` ` ` `// be used to get a sum x.` ` ` `// Updating the count of remainders.` ` ` `rem[a[i] % x]++;` ` ` `}` ` ` `}` ` ` ` ` `// Traversing the remainder list` ` ` `// from start to middle to` ` ` `// find pairs` ` ` `for` `(i = 1; i < x / 2; i++)` ` ` `{` ` ` `if` `(rem[i] > 0 && rem[x - i] > 0)` ` ` `{` ` ` ` ` `// The elements with remainders` ` ` `// i and x-i will` ` ` `// result to a sum of x.` ` ` `// Once we get two` ` ` `// elements which add up to x ,` ` ` `// we print x and` ` ` `// break.` ` ` `cout << ` `"Yes"` ` ` `<< ` `"\n"` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` ` ` `// Once we reach middle of` ` ` `// remainder array, we have to` ` ` `// do operations based on x.` ` ` `if` `(i >= x / 2)` ` ` `{` ` ` `if` `(x % 2 == 0)` ` ` `{` ` ` `if` `(rem[x / 2] > 1)` ` ` `{` ` ` ` ` `// if x is even and` ` ` `// we have more than 1` ` ` `// elements with remainder` ` ` `// x/2, then we will` ` ` `// have two distinct elements` ` ` `// which add up` ` ` `// to x. if we dont have` ` ` `//more than 1` ` ` `// element, print "No".` ` ` `cout << ` `"Yes"` ` ` `<< ` `"\n"` `;` ` ` `}` ` ` `else` ` ` `{` ` ` `cout << ` `"No"` ` ` `<< ` `"\n"` `;` ` ` `}` ` ` `}` ` ` `else` ` ` `{` ` ` ` ` `// When x is odd we continue` ` ` `// the same process` ` ` `// which we did in previous loop.` ` ` `if` `(rem[x / 2] > 0 &&` ` ` `rem[x - x / 2] > 0)` ` ` `{` ` ` `cout << ` `"Yes"` ` ` `<< ` `"\n"` `;` ` ` `}` ` ` `else` ` ` `{` ` ` `cout << ` `"No"` ` ` `<< ` `"\n"` `;` ` ` `}` ` ` `}` ` ` `}` `}` `/* Driver Code */` `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;` `}` `// This article is contributed by Sai Sanjana Gudla` |

**Output**

Yes

**Time Complexity: **O(n+x)

**Auxiliary Space: **O(x)

Last Updated on October 16, 2021 by admin