- 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.

## 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.

## 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