Key Pair

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro