QUESTION

Given an array A[] of n numbers and another number x, determine whether or not there exist two elements in A whose sum is exactly x.\n\nInput:\n\nThe first line of input contains an integer T denoting the number of test cases.\nThe first line of each test case is N and X,N is the size of array.\nThe second line of each test case contains N integers representing array elements C[i].\n\nOutput:\n\nPrint \”Yes\” if there exist two elements in A whose sum is exactly x, else \”No\” without quotes.\n\nConstraints:\n\n1 T 100\n1 N 200\n1 C[i] 1000.

“TESTCASE_1”: “2\n6 16\n1 4 45 6 10 8\n5 10\n1 2 4 3 6\n###—###SEPERATOR—###—\nYes\nYes”, “TESTCASE_2”: “2\n6 10\n1 3 57 9 13 6\n5 8\n1 5 9 3 7\n###—###SEPERATOR—###—\nYes\nYes”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

# 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 t;
  scanf("%d", &t);
  while(t--)
  {
    int arr_size, n;
    scanf("%d %d", &arr_size, &n);
    int A[n], i;
    for(i=0; i<arr_size; i++)
      scanf("%d", &A[i]);
    
    
    if( hasArrayTwoCandidates(A, arr_size, n))
        printf("Yes\n");
    else
        printf("No\n");
 
    getchar();
  }
    return 0;
}