Ask Question
13 August, 04:42

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?

+4
Answers (1)
  1. 13 August, 07:50
    0
    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
    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

    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<
    / / 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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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, ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers