Question

(Linear time algorithm for finding duplicates of two sorted arrays, 20pt)

Devise a linear time O(m+n) algorithm to find the duplicates between two sorted arrays (m, n are the sizes of two arrays). For instance, for inputs {1,3,5,7} and {1,2,3,4}, the correct outputs should be {1,3

Answer 1

/* Code of the above question in C language */
  
#include<stdio.h>
/* This function prints Duplicates of arr1[] and arr2[]
where,
    m is the number of elements in arr1[]
   n is the number of elements in arr2[]
*/
   
void printDuplicates(int arr1[], int arr2[], int m, int n)
{
   int i = 0;
  
   int j = 0;
  
   while (i < m && j < n)
   {
       if(arr1[i] == arr2[j]) /* if both the elements are equal (Duplicates)*/
       {
           /* printing the element */
           printf(" %d ", arr1[i]);
             
           /* incrementing both i,j */
           i++;
           j++;
       }
          
       else if(arr1[i] < arr2[j]) /* if arr1[i] is smaller than arr2[j] */
       {
           /* incrementing index i */
           i++;
       }
          
       else if (arr2[j] < arr1[i]) /* if arr1[i] is larger than arr2[j] */
       {
           /* incrementing index j */
           j++;
       }
   }
}
  

int main()
{
   int m,n; /* Declaring the two variables, which are sizes of two arrays*/
  
   /* Reading the size of array1 from User*/
   printf(" Enter m : ");
   scanf("%d",&m);

   /* Reading the size of array2 from User*/
   printf(" Enter n : ");
   scanf("%d",&n);
      
    int arr1[m]; /* Declaring array1 of size 'm' */
   
    int arr2[n]; /* Declaring array2 of size 'n' */
   
    printf(" Enter elements for array1 : \n");
   
    /* Reading the array1 from the User*/
    for(int i=0; i<m; ++i)
        scanf("%d",&arr1[i]);
   
    printf(" Enter elements for array2 : \n");
       
    /* Reading the array2 from the User*/
    for(int i=0; i<n; ++i)
        scanf("%d",&arr2[i]);
  
   /* Calling our required function */
   printDuplicates(arr1, arr2, m, n);
}