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?

Question

Computers and Technology

Lorelai Fitzgerald

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)

Know the Answer?

Todd Carlson · Answer 1

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