Thursday, 30 March 2017

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

Tags

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:

 


EmoticonEmoticon