Question

Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5. What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, respectively?

Answer 1

Answer:

Algorithm:

1. Declare and initial two array a, b of length m, n.

2.sort both the array.

3.Create and initial two variables i=0,j=0.

4. while(i<m and j<n)

   4.1 if a[i] equal b[j], increase both i and j by 1.

   4.2 if a[i] > b[j] then increase j

   4.3 else increase i

5. End the program.

Here maximum number of comparison will O<=(m+n) if there will be no common element in both the array.In the while loop, i will maximum goes to m And j will maximum to n.In each loop i will increase or j will increase or both

increase.

// here is code in c++ to implemented the above algorithm

#include <bits/stdc++.h>

using namespace std;

int main() {

   

   // declare and initialize two array

 int ar[] = { 2, 5, 5, 5 };

 int br[] = { 2, 2, 3, 5, 5, 7 };

 int i = 0;

 int j = 0;

 int m=sizeof(ar)/sizeof(ar[0]);

 int n=sizeof(br)/sizeof(br[0]);

 cout<<"Common elements are:";

 // use while loop, to check the

 // array elements

 while (i < m && j < n)

 {

    if (ar[i] == br[j])

       {

           // display an array element

           cout<<ar[i]<<" ";

           // Increment variables          

           i++;

           j++;

   

       }

    else if (ar[i] > br[j])

           j++;

   else

       i++;

         } // end of while

return 0;

}

Output:

Common elements are:2 5 5