Can someone explain this, I was at another website explaining this. But one of t
ID: 3747332 • Letter: C
Question
Can someone explain this, I was at another website explaining this. But one of the libarires they used was for a different IDE and I am not allowed to use that type of IDE so, I became lost when reading it.
Problem 3: Given an array A, and a number x, check for pair in A with sum as ». Algorithm hasArrayTwoCandidates (A[], ar size, sum) 1) Sort the array in non-decreasing order. 2) Initialize two index variables to find the candidate elements in the sorted array t to the leftmost index: (a) Initialize firs - (b) Initialize second the rightmost index: r-ar_size-1 3) Loop whileExplanation / Answer
Hello,
As you did not mention that what programming language you used I will implement your given algo in C which is known by most of the programmer
And you mention about IDE so i will make it with satandard procedure which is excepted in every IDE
And if you not understand it further please comment about your language and IDE
Now lets discuss your problem and solution to your algorthim
Problem:we have an array of integer and we need to find that any pair of element have sum equal to given sum or not.
now lets discuss your algo with your example
A[] ={1,4,45,6,10,-8} and given sum = 46
Step 1: First of all we sort the array in non-decreaing order, it give us guarantee that for any index i A[i]<A[i+1]
so our array become
A[] = {-8,1,4,6,10,45}
now we take two vaiable l and r
l stores the index of smallest element of Array i.e. l=0;
and r stores the index of largest element of Array i.e. r=arr_size-1
Now we check that what is the sum of A[l]+A[r]
now there are 3 possibility
A. A[l]+A[r] is equal to given sum: this is our moto if we find it return 1 to indicate tha we find given sum as sum of two element in array
B. A[l]+A[r] < sum that means to get sum we need to add bigger value since A[r] is maximum so we increment value of l because we know A[l+1]>=A[l]
C. A[l]+A[r] > sum that means to get sum we need to add small value since A[l] is minimum so we decrement value of r because we know A[r]>=A[r+1]
in our example
when l=0 and r=5
A[l]+A[r] = -8 + 45 =37 which is less than given sum 46 so we increment value of l
now l=1 and r= 5
A[l]+A[r] = 1+45 = 46 whiich is equal to given sum so we return 1
and output get printed
// Implement of Algo in C
#include <stdio.h>
void sort(int A[], int arr_size)
{
//using insertion sort algo to sort element of array
int i,j,temp;
for(i=0;i<arr_size;i++)
{
temp = A[i];
j=i-1;
while(j>=0 && A[j]>temp)
{
A[j+1] = A[j];
j--;
}
A[j+1] = temp;
}
}
//function implement given algorthim
int hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
//for sum we need two variable, so l is defined index of left operend
//and r is defined index of right operend
int l, r;
sort(A,arr_size); //sort the array
l = 0;
r = arr_size-1;
while (l < r)
{
if(A[l] + A[r] == sum)
return 1; //return 1 if we found sum
else if(A[l] + A[r] < sum)
l++; //if A[l]+ A[r] is less than sum then we increment value of l since array is sorted than A[l]<=A[l+1]
else
r--;//if A[l]+ A[r] is greater than sum then we decrement value of r since array is sorted than A[r]>=A[r-1]
}
return 0;
}
//Main function of program
int main()
{
int A[] = {1, 4, 45, 6, 10, -8};
int sum = 16;
int arr_size = 6;
if( hasArrayTwoCandidates(A, arr_size, sum)==1)
printf("Array has two elements with given sum");
else
printf("Array doesn't have two elements with given sum");
return 0;
}