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

Answer 2

Below is the required program code of C++.

C++ language

Program:

//Creating header files

#include <bits/stdc++.h>

using namespace std;

//Main method

int main()

{

//Declaring and Initiating two arrays

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:";

//Using while loop, to check the array elements

while (i < m && j < n)

{

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

      {

          //Displaying an elements of array

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

          //Increment variables          

          i++;

          j++;

      }

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

          j++;

  else

      i++;

        }

        //End of while loop

return 0;

}

Program explanation:

• Creating header files.
• Defining Main method.
• Declaring and Initiating two arrays.
• Using while loop, to check the array elements.
• Displaying an elements of array and increment the variable.
• End of while loop.
• End of program.

Output:

Find below the attachment of the output.

Find out more information about C++ here:

https://brainly.com/question/24953880