Given an array A[] and a number x, check for pair in A[] with sum as x

Given an array A[] and a number x, check for pair in A[] with sum as x

METHOD 1 (Use Sorting)

# include <stdio.h>

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

}

Output:

Array has two elements with the given sum

METHOD 2 (Use Hashing)

// Works only if range elements is limited

#include <stdio.h>

#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[0]);

    printPairs(A, arr_size, n);

     getchar();

    return 0;

}

Output:

Pair with given sum 16 is (10, 6)