# C Program to check whether an sorted array conatins two element whose sum is equal to an element K

This question can be solved in O(n) time and O(1) space by using this approach. Approach is simple we will traverse the array till we found the element greater than  K and this way we will get upper bound. Algorithm to check whether an sorted array contains two element whose sum is equal to an element K or not is given below. If we found such two elements then we return print 1 otherwise -1.

Algorithm:

/* Care of index 0 is taken */

set:  beg=0,end=0;
doWhile   arr[beg]<K:
set: end=end+1
set: beg=beg+1
EndWhile

set: end=end-1
set: beg=0

doWhile   beg<end:
if  arr[beg]+arr[end]=x:
return 1
else If  arr[beg]+arr[end]<x:
set: beg=beg+1
else
set: end=end-1
EndWhile
return -1    /*If such two element has not found during the traversal we will return -1*/

Time Complexity: O(n)
Space Complexity: O(1)

Note: If  size of array is already given to you then you can also use the binary search to find the upper bound and save more iterations.

Explanation of the above algorithm:

Let   A[]= { 3, 6, 8, 13, 15, 21 }
Let   K=19

First loop     while(arr[beg]<K)

Pass 1, beg=0:      arr[0]=3   less than K . Therefore end will be incremented.   end=1
Pass 2, beg=1:      arr[1]=6   less than K.  Therefore end will be incremented.   end=2
Pass 3, beg=2:      arr[2]=8   less than K.  Therefore end will be incremented.   end=3
Pass 4, beg=3:      arr[3]=13 less than K.  Therefore end will be incremented.   end=4
Pass 5, beg=4:      arr[4]=15 less than K.  Therefore end will be incremented.   end=5

Now first loop will terminate as beg becomes 5 but arr[5]>K

set:   beg=0
set:   end=end-1=4  /*because we have to take care of index 0 */

Second loop   while(beg<end)

Pass 1, beg=0, end=4:   arr[0]+arr[4]=3+15=18  which is less than K. Therefore set: beg=beg+1
Pass 2, beg=1, end=4:   arr[1]+arr[4]=6+15=21  which is greater than K. Therefore set: end=end-1
Pass 3, beg=1, end=3:   arr[1]+arr[3]=6+13=19  which is equal to K. Therefore, we will return 1.

C Program to check whether an array contains two elements whose sum is equal to element K or not:-

```#include <stdio.h>
#define MAX 100
int findsum(int arr[],int x);
int main()
{
int arr[MAX],n,i,x,result;

printf("\nEnter the total number of elements: \n");
scanf("%d",&n);

printf("\nEnter the elements: \n");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}

printf("\nGiven array is: \n");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("\nEnter the x: ");
scanf("%d",&x);
result=findsum(arr,x);
printf("\n\n%d",result);
return 0;
}
int findsum(int arr[],int x)
{
int beg=0,end=0;
while(arr[beg]<x)
{
end++;
beg++;
}
end=end-1;
beg=0;
while(beg<end)
{
if(arr[beg]+arr[end]==x)
{
return 1;
}
else if(arr[beg]+arr[end]<x)
{
beg++;
}
else
{
end--;
}
}
return -1;
}
```

OUTPUT: