# 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 S whose sum is exactly x.

METHOD 1 (Use Sorting)

Algorithm :

```hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate
elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second  the rightmost index:  r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == sum)  then return 1
(b) Else if( A[l] + A[r] <  sum )  then l++
(c) Else r--
4) No candidates in whole array - return 0
```

Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.
Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

Example :

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

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

Initialize l = 0, r = 5
A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 10
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 are more than one pair having the given sum then this algorithm reports only one. Can be easily extended for this though.

Below is the implementation of the above approach.

## C++

 `// C++ program to check if given array  ` `// has 2 elements whose sum is equal  ` `// to the given value ` ` `  `#include ` `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); ` `     `  `    ``// 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; ` `} `

## C

 `// C program to check if given array  ` `// has 2 elements whose sum is equal  ` `// to the given value ` ` `  `# include ` `# define bool int ` ` `  `void` `quickSort(``int` `*, ``int``, ``int``); ` ` `  `bool` `hasArrayTwoCandidates(``int` `A[], ``int` `arr_size, ``int` `sum) ` `{ ` `    ``int` `l, r; ` ` `  `    ``/* Sort the elements */` `    ``quickSort(A, 0, arr_size-1); ` ` `  `    ``/* 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; ` `} ` ` `  `/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING  ` `    ``PURPOSE */` `void` `exchange(``int` `*a, ``int` `*b) ` `{ ` `    ``int` `temp; ` `    ``temp = *a; ` `    ``*a   = *b; ` `    ``*b   = temp; ` `} ` ` `  `int` `partition(``int` `A[], ``int` `si, ``int` `ei) ` `{ ` `    ``int` `x = A[ei]; ` `    ``int` `i = (si - 1); ` `    ``int` `j; ` ` `  `    ``for` `(j = si; j <= ei - 1; j++) ` `    ``{ ` `        ``if``(A[j] <= x) ` `        ``{ ` `            ``i++; ` `            ``exchange(&A[i], &A[j]); ` `        ``} ` `    ``} ` `    ``exchange (&A[i + 1], &A[ei]); ` `    ``return` `(i + 1); ` `} ` ` `  `/* Implementation of Quick Sort ` `A[] --> Array to be sorted ` `si  --> Starting index ` `ei  --> Ending index ` `*/` `void` `quickSort(``int` `A[], ``int` `si, ``int` `ei) ` `{ ` `    ``int` `pi;    ``/* Partitioning index */` `    ``if``(si < ei) ` `    ``{ ` `        ``pi = partition(A, si, ei); ` `        ``quickSort(A, si, pi - 1); ` `        ``quickSort(A, pi + 1, ei); ` `    ``} ` `} ` ` `  `/* Driver program to test above function */` `int` `main() ` `{ ` `    ``int` `A[] = {1, 4, 45, 6, 10, -8}; ` `    ``int` `n = 16; ` `    ``int` `arr_size = 6; ` `    `  `    ``if``( hasArrayTwoCandidates(A, arr_size, n)) ` `        ``printf``(``"Array has two elements with given sum"``); ` `    ``else` `        ``printf``(``"Array doesn't have two elements with given sum"``); ` ` `  `    ``getchar``(); ` `    ``return` `0; ` `} `

## Java

 `// Java program to check if given array  ` `// has 2 elements whose sum is equal  ` `// to the given value ` `import` `java.util.*; ` ` `  `class` `GFG ` `{ ` `    ``// Function to check if array has 2 elements  ` `    ``// whose sum is equal to the given value ` `    ``static` `boolean` `hasArrayTwoCandidates(``int` `A[],  ` `                           ``int` `arr_size, ``int` `sum) ` `    ``{ ` `        ``int` `l, r; ` `     `  `        ``/* Sort the elements */` `        ``Arrays.sort(A); ` `     `  `        ``/* 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` `true``;  ` `            ``else` `if``(A[l] + A[r] < sum) ` `                ``l++; ` `            ``else` `// A[i] + A[j] > sum ` `                ``r--; ` `        ``}  ` `        ``return` `false``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `A[] = {``1``, ``4``, ``45``, ``6``, ``10``, -``8``}; ` `        ``int` `n = ``16``; ` `        ``int` `arr_size = A.length; ` `         `  `        ``// Function calling ` `        ``if``(hasArrayTwoCandidates(A, arr_size, n)) ` `            ``System.out.println(``"Array has two "` `+  ` `                               ``"elements with given sum"``); ` `        ``else` `            ``System.out.println(``"Array doesn't have "` `+ ` `                               ``"two elements with given sum"``); ` `     `  `    ``} ` ` `  `} `

## Python

 `# Python program to check for the sum condition to be satisified ` ` `  `def` `hasArrayTwoCandidates(A,arr_size,``sum``): ` `     `  `    ``# sort the array ` `    ``quickSort(A,``0``,arr_size``-``1``) ` `    ``l ``=` `0` `    ``r ``=` `arr_size``-``1` `     `  `    ``# traverse the array for the two elements ` `    ``while` `l Array to be sorted ` `# si  --> Starting index ` `# ei  --> Ending index ` `def` `quickSort(A, si, ei): ` `    ``if` `si < ei: ` `        ``pi``=``partition(A,si,ei) ` `        ``quickSort(A,si,pi``-``1``) ` `        ``quickSort(A,pi``+``1``,ei) ` ` `  `# Utility function for partitioning the array(used in quick sort) ` `def` `partition(A, si, ei): ` `    ``x ``=` `A[ei] ` `    ``i ``=` `(si``-``1``) ` `    ``for` `j ``in` `range``(si,ei): ` `        ``if` `A[j] <``=` `x: ` `            ``i ``+``=` `1` `             `  `            ``# This operation is used to swap two variables is python ` `            ``A[i], A[j] ``=` `A[j], A[i] ` ` `  `        ``A[i``+``1``], A[ei] ``=` `A[ei], A[i``+``1``] ` `         `  `    ``return` `i``+``1` `     `  ` `  `# Driver program to test the functions ` `A ``=` `[``1``,``4``,``45``,``6``,``10``,``-``8``] ` `n ``=` `16` `if` `(hasArrayTwoCandidates(A, ``len``(A), n)): ` `    ``print``(``"Array has two elements with the given sum"``) ` `else``: ` `    ``print``(``"Array doesn't have two elements with the given sum"``) ` ` `  `## This code is contributed by __Devesh Agrawal__ `

## C#

 `// C# program to check for pair  ` `// in A[] with sum as x ` ` `  `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``static` `bool` `hasArrayTwoCandidates(``int` `[]A,  ` `                             ``int` `arr_size, ``int` `sum) ` `    ``{ ` `        ``int` `l, r; ` `         `  `        ``/* Sort the elements */` `        ``sort(A, 0, arr_size-1); ` `         `  `        ``/* 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` `true``;  ` `            ``else` `if``(A[l] + A[r] < sum) ` `                ``l++; ` `            ``else` `// A[i] + A[j] > sum ` `                ``r--; ` `        ``}  ` `        ``return` `false``; ` `    ``} ` `     `  `    ``/* Below functions are only to sort the  ` `    ``array using QuickSort */` `         `  `    ``/* This function takes last element as pivot, ` `    ``places the pivot element at its correct ` `    ``position in sorted array, and places all ` `    ``smaller (smaller than pivot) to left of ` `    ``pivot and all greater elements to right ` `    ``of pivot */` `    ``static` `int` `partition(``int` `[]arr, ``int` `low, ``int` `high) ` `    ``{ ` `        ``int` `pivot = arr[high];  ` `     `  `        ``// index of smaller element ` `        ``int` `i = (low-1);  ` `        ``for` `(``int` `j = low; j <= high - 1; j++) ` `        ``{ ` `            ``// If current element is smaller ` `            ``// than or equal to pivot ` `            ``if` `(arr[j] <= pivot) ` `            ``{ ` `                ``i++; ` `     `  `                ``// swap arr[i] and arr[j] ` `                ``int` `temp = arr[i]; ` `                ``arr[i] = arr[j]; ` `                ``arr[j] = temp; ` `            ``} ` `        ``} ` `     `  `        ``// swap arr[i+1] and arr[high] (or pivot) ` `        ``int` `temp1 = arr[i+1]; ` `        ``arr[i+1] = arr[high]; ` `        ``arr[high] = temp1; ` `     `  `        ``return` `i+1; ` `    ``} ` `     `  `    ``/* The main function that  ` `    ``implements QuickSort() ` `    ``arr[] --> Array to be sorted, ` `    ``low --> Starting index, ` `    ``high --> Ending index */` `    ``static` `void` `sort(``int` `[]arr, ``int` `low, ``int` `high) ` `    ``{ ` `        ``if` `(low < high) ` `        ``{ ` `            ``/* pi is partitioning index, arr[pi]  ` `            ``is now at right place */` `            ``int` `pi = partition(arr, low, high); ` `     `  `            ``// Recursively sort elements before ` `            ``// partition and after partition ` `            ``sort(arr, low, pi-1); ` `            ``sort(arr, pi+1, high); ` `        ``} ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]A = {1, 4, 45, 6, 10, -8}; ` `        ``int` `n = 16; ` `        ``int` `arr_size = 6; ` `         `  `        ``if``( hasArrayTwoCandidates(A, arr_size, n)) ` `            ``Console.Write(``"Array has two elements"``+  ` `                        ``" with given sum"``); ` `        ``else` `            ``Console.Write(``"Array doesn't have "``+ ` `                       ``"two elements with given sum"``); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by Sam007  `

## PHP

 ` sum ` `            ``\$r``--; ` `    ``}  ` `    ``return` `0; ` `} ` ` `  `// Driver Code ` `\$A` `= ``array` `(1, 4, 45, 6, 10, -8); ` `\$n` `= 16; ` `\$arr_size` `= sizeof(``\$A``); ` ` `  `// Function calling ` `if``(hasArrayTwoCandidates(``\$A``, ``\$arr_size``, ``\$n``)) ` `    ``echo` `"Array has two elements "` `. ` `                   ``"with given sum"``; ` `else` `    ``echo` `"Array doesn't have two "` `.  ` `          ``"elements with given sum"``; ` `     `  `// This code is contributed by m_kit ` `?> `

Output :

`Array has two elements with the given sum`

METHOD 2 (Use Hashing)
This method works in O(n) time.

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

Below is the implementation of the above approach :

## C++

 `// C++ program to check if given array ` `// has 2 elements whose sum is equal ` `// to the given value ` `#include ` ` `  `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` `(temp >= 0 && s.find(temp) != s.end()) ` `            ``cout << ``"Pair with given sum "` `<< sum << ` `                 ``" is ("` `<< arr[i] << ``", "` `<< temp << ` `                 ``")"` `<< endl; ` ` `  `        ``s.insert(arr[i]); ` `    ``} ` `} ` ` `  `/* 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); ` ` `  `    ``// Function calling ` `    ``printPairs(A, arr_size, n); ` ` `  `    ``return` `0; ` `} `

## C

 `// C++ program to check if given array  ` `// has 2 elements whose sum is equal  ` `// to the given value ` ` `  `// Works only if range elements is limited ` `#include ` `#define MAX 100000 ` ` `  `void` `printPairs(``int` `arr[], ``int` `arr_size, ``int` `sum) ` `{ ` `  ``int` `i, temp; ` `  ``bool` `s[MAX] = {0}; ``/*initialize hash set as 0*/` ` `  `  ``for` `(i = 0; i < arr_size; i++) ` `  ``{ ` `      ``temp = sum - arr[i]; ` `      ``if` `(temp >= 0 && s[temp] == 1) ` `         ``printf``(``"Pair with given sum %d is (%d, %d) n"``,  ` `                 ``sum, arr[i], temp); ` `      ``s[arr[i]] = 1; ` `  ``} ` `} ` ` `  `/* 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); ` ` `  `    ``printPairs(A, arr_size, n); ` ` `  `    ``getchar``(); ` `    ``return` `0; ` `} `

## Java

 `// Java implementation using Hashing ` `import` `java.io.*; ` `import` `java.util.HashSet; ` ` `  `class` `PairSum ` `{ ` `    ``static` `void` `printpairs(``int` `arr[],``int` `sum) ` `    ``{        ` `        ``HashSet s = ``new` `HashSet(); ` `        ``for` `(``int` `i=``0``; i=``0` `&& s.contains(temp)) ` `            ``{ ` `                ``System.out.println(``"Pair with given sum "` `+ ` `                                    ``sum + ``" is ("` `+ arr[i] + ` `                                    ``", "``+temp+``")"``); ` `            ``} ` `            ``s.add(arr[i]); ` `        ``} ` `    ``} ` ` `  `    ``// Main to test the above function ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``int` `A[] = {``1``, ``4``, ``45``, ``6``, ``10``, ``8``}; ` `        ``int` `n = ``16``; ` `        ``printpairs(A,  n); ` `    ``} ` `} ` ` `  `// This article is contributed by Aakash Hasija `

## Python

 `# Python program to find if there are ` `# two elements wtih given sum ` ` `  `# function to check for the given sum ` `# in the array ` `def` `printPairs(arr, arr_size, ``sum``): ` `     `  `    ``# Create an empty hash set ` `    ``s ``=` `set``() ` `     `  `    ``for` `i ``in` `range``(``0``,arr_size): ` `        ``temp ``=` `sum``-``arr[i] ` `        ``if` `(temp>``=``0` `and` `temp ``in` `s): ` `            ``print` `(``"Pair with the given sum is"``, arr[i], ``"and"``, temp) ` `        ``s.add(arr[i]) ` ` `  `# driver program to check the above function ` `A ``=` `[``1``,``4``,``45``,``6``,``10``,``8``] ` `n ``=` `16` `printPairs(A, ``len``(A), n) ` ` `  `# This code is contributed by __Devesh Agrawal__ `

## C#

 `// C# implementation using Hashing ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `static` `void` `printpairs(``int` `[]arr, ` `                       ``int` `sum) ` `{      ` `    ``HashSet<``int``> s = ``new` `HashSet<``int``>(); ` `    ``for` `(``int` `i = 0; i < arr.Length; ++i) ` `    ``{ ` `        ``int` `temp = sum - arr[i]; ` ` `  `        ``// checking for condition ` `        ``if` `(temp >= 0 && s.Contains(temp)) ` `        ``{ ` `            ``Console.Write(``"Pair with given sum "` `+ ` `                          ``sum + ``" is ("` `+ arr[i] + ` `                               ``", "` `+ temp + ``")"``); ` `        ``} ` `        ``s.Add(arr[i]); ` `    ``} ` `} ` ` `  `// Driver Code ` `static` `void` `Main () ` `{ ` `    ``int` `[]A = ``new` `int``[]{1, 4, 45,  ` `                        ``6, 10, 8}; ` `    ``int` `n = 16; ` `    ``printpairs(A, n); ` `} ` `}  ` ` `  `// This code is contributed by ` `// Manish Shaw(manishshaw1) `

Output:

`Pair with given sum 16 is (10, 6)`

Time Complexity: O(n)
Auxiliary Space: O(n) where n is size of array.

If range of numbers include negative numbers then also it works. All we have to do for negative numbers is to make everything positive by adding the absolute value of smallest negative integer to all numbers.

Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.

This article is attributed to GeeksforGeeks.org

code

load comments