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
Posted by
Labels: ,