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