Let A and B be two sorted arrays, each with n elements. You have to write an eff

Question

Let A and B be two sorted arrays, each with n elements. You have to write an efficient algorithm which finds out if A and B have any elements in common. For example if A = [4.7,12,15], B = [2,4.6,23000] the answer should be yes (since 4 is an element in common), if A = [4.7,900]. B = [2,3, 28] the answer should be no. In terms of efficiency, the faster your algorithm Is, the better. You will get hill credit if your algorithm is correct and works in time O(n). You will get substantial partial credit if your algorithm Ls correct and works in time smaller than 0(n2) but bigger than O(n). You will get some partial credit if your algorithm is correct and works in time 0(n2). Give a clear description of your algorithm for the above problem. TVace how your algorithm works on the above two examples. Do a worst case time analysis (use big O notation) of your algorithm.

Explanation / Answer

For common of two arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.

int common(int arr1[], int arr2[], int m, int n)

{

  int i = 0, j = 0;

  while(i < m && j < n)

  {

    if(arr1[i] < arr2[j])

      i++;

    else if(arr2[j] < arr1[i])

      j++;

    else /* if arr1[i] == arr2[j] */

    {

      printf(" %d ", arr2[j++]);

      i++;

    }

  }

}

this will take O(m+n)

if m=n then, O(2n)= O(n)

2 method

you can use hashing also

this will take spaces complexity of O(m)

and searching time O(n)

create an array set upto m elements ( choose the array to create set such that m<n ; so that space is reduced)

now hash each element in other array and check for the presence in created array set

if they match, we have common

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.