Target Sums Given a sorted array of n distinct values as well as a target value
ID: 668721 • Letter: T
Question
Target Sums Given a sorted array of n distinct values as well as a target value T, determine in O(n) time whether or not there exist two distinct values in the array that sum to T. (For example, if the array contained 3, 5, 6, 7, and 9 and T 14, then you should report that a pair of values in the array exists that adds up to T. If T 17, you should indicate that no such pair exists. Input Format The first line of the file will have a single positive integer k, representing the number of test cases in the file. Each test case will follow. The first line of each test case will have two space separated positive integers: n (n s 106), the size of the array, and t (ts 10%, the target for the input case. The following n distinct positive integers will be listed in ascending order, separated by white space. Output Format For each test case, output a line with either YES or No depending on whether or not there exist two distinct integers in the given array that add up to the designated target. Sample Input 5 14 3 5 6 79 3 11 1 3 6 Sample Output YES NO Assignment Details Please use standard in, standard out. If you choose to submit this one (you must submit one of RP 1-4), please call your submission tal et.cExplanation / Answer
// Program
#include <stdio.h>
#include <stdbool.h>
#define MAX 1000
bool CheckPairs(int[], int , int );
int main()
{
// Opening testcases file and read it to assign the values to proper
//holders
FILE *fp,*fp1;
int testcases,i,j;
fp=fopen("arrinput.txt", "r"); // Note: create arrinput.txt file in proper directory
fscanf(fp,"%d",&testcases);
int A[testcases][5];
int n[testcases];
int T[testcases];
for(i=0;i<testcases;i++)
{
fscanf(fp,"%d%d",&n[i],&T[i]); // reading array size and target value
for(j=0;j<n[i];j++)
{
fscanf(fp,"%d",&A[i][j]); // reading array elements
}
}
//Checking the pairs and write the output to result file
fp1=fopen("arroutput.txt", "w");
for(i=0;i<testcases;i++)
{
if( CheckPairs(A[i], n[i], T[i])) // call to check pair
fprintf(fp1,"YES "); // pair available
else
fprintf(fp1,"NO "); // pair not available
}
getchar();
return 0;
}
// check a pair with sum equals to target value
bool CheckPairs(int A[], int n, int T)
{
int i, temp;
bool flag=false;
/*initialize hash map as 0*/
bool binMap[MAX] = {0};
for(i = 0; i < n; i++)
{
temp = T - A[i];
if(temp >= 0 && binMap[temp] == 1)
{
flag=true;
break;
}
binMap[A[i]] = 1;
}
return flag;
}
---------------------------------------------------------------------------------------------------------
//arrinput.txt
2
5 14
3 5 6
7 9
3 11
------------------------------------------------------------------------------------------------------------------------
//arroutput.txt
YES
NO
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.