# Program to Find a Pair Whose Sum is Equal to Given Number

• Write a program to find pair of numbers in an array whose sum is K
• Write a function to check whether a pair of numbers exists whose sum is K

Given an integer array of size N we have to check whether a pair of array elements exist whose sum is K.
For Example :

```Input Array : 7 2 4 1 3
K = 8
Output :
Found Pair : 1 7
```

Let inputArray be an integer array of size N and we want to find a pair whose sum is K.

Using Hash Table
• In this algorithm we will use a Hash Table to store all the previously visited array elements. By using hash table, we can check whether we previously visited element X or not in inputArray in O(1) time. We will start with an empty hash table.
• Using a loop, traverse inputArray and for every element E check whether K-E is present in hash table.
• If K-E is present in hash table then we found one pair else put E in hash table.
Time Complexity : O(n)

## C program to find a pair of number whose sum is K using hash table

```#include <stdio.h>
#define ARRAY_SIZE 100000

void hasSumPair(int array[], int size, int sum) {
int i;
/* NOTE : here we are assuming that all numbers
in input array are less than 100000 */
int table[ARRAY_SIZE] = {0};

for (i = 0; i < size; i++) {
if(table[sum-array[i]] == 1 && sum-array[i] >= 0) {
printf("Found Pair : %d %d\n", array[i], sum-array[i]);
}
table[array[i]] = 1;
}
}

int main(){
int i, array[1000], count, sum;
printf("Enter the number of elements in Array\n");
scanf("%d", &count);

printf("Enter %d numbers\n", count);
for(i = 0; i < count; i++){
scanf("%d", &array[i]);
}

printf("Enter the value of sum\n");
scanf("%d", &sum);

hasSumPair(array, count, sum);

return 0;
}
```
Output
```Enter the number of elements in Array
6
Enter 6 numbers
7 2 4 3 1 5
Enter the value of sum
8
Found Pair : 1 7
Found Pair : 5 3
```

By Sorting Input Array
• Sort inputArray using any O(nLogn) time sorting algorithm.
• Initialize leftIndex and rightIndex to 0 and N-1 respectively.
• If inputArray[leftIndex] + inputArray[rightIndex] is equal to K, then we found a pair.
• If inputArray[leftIndex] + inputArray[rightIndex] is less than K, then increment leftIndex else decrement rightIndex.
• Continue until leftIndex is less than rightIndex.
Time Complexity : O(nLogn)

## C program to find a pair of number whose sum is K using sorting

```#include <stdio.h>
#include <stdlib.h>

/* This function will be used as a comparator
function by qsort function */
int compare(const void* one, const void* two) {
return *(int*)one > *(int*)two;
}

int hasSumPair(int array[], int size, int sum) {
int left, right, currentSum;

/* sort input array */
qsort(array, size, sizeof(int), compare);

/* Initialize left and right to first and
last index of array */
left = 0;
right = size-1;
while(left < right) {
currentSum = array[left] + array[right];
/*Check if sun of array[left] and array[right]
is equal to sum */
if(currentSum == sum) {
return 1;
} else if(currentSum < sum) {
/* If currentSum < sum, then increase the value
of currentSum by incrementing left index */
left++;
} else {
/* currentSum is greater than sum, decrease
value of currentsum by decrementing right index */
right--;
}
}
return 0;
}

int main(){
int i, array[1000], count, sum;
printf("Enter the number of elements in Array\n");
scanf("%d", &count);

printf("Enter %d numbers\n", count);
for(i = 0; i < count; i++){
scanf("%d", &array[i]);
}

printf("Enter the value of sum\n");
scanf("%d", &sum);

if(hasSumPair(array, count, sum)){
printf("Found two elements whose sum equals %d", sum);
} else {
printf("Not Found two elements whose sum equals %d", sum);
}

return 0;
}
```
Output
```Enter the number of elements in Array
6
Enter 6 numbers
7 4 1 9 3 2
Enter the value of sum
6
Found two elements whose sum equals 6
```
```Enter the number of elements in Array
7
Enter 7 numbers
9 2 1 6 4 8 3
Enter the value of sum
100
Not Found two elements whose sum equals 100
```