Question

Complete this function (the instructions are below the code):

private static int numCommonElements(int A[], int B[], int lenA, int lenB) {
// Complete this function.
}

We want to solve the following problem: given two sorted arrays A[n] and B[m] of length n and m respectively, we want to nd the number of elements that are common to both the arrays (without repeated counting of the same element).
For example, the arrays A[ ] = {7; 13; 19; 20; 22; 22; 37; 37} and B[ ] = {7; 14; 17; 22; 28; 31; 37; 37; 37; 43}, both have 7, 22 and 37; hence, the count is 3. (Note that we count 22 and 37 only once.)
On the other hand, A[ ] = {7; 13; 19; 20; 22} and B[ ] = {14; 17; 21; 28} have nothing in common; hence, the count is 0.
One algorithm for solving this problem is as follows: pick each number in array A and then scan array B to verify if the number exists. It is easy to see that the Big-O complexity of this procedure is O(mn). As you may have guessed, this algorithm is pretty slow.
Our task is to devise a faster algorithm, based on binary search. To this end, complete the following function:
- int numCommonElements(int A[ ], int B[ ], int lenA, int lenB): returns the number of elements that are present in both arrays A and B. Returns 0 if none of the elements are
common. It should not double count any element.
Caution: You algorithm must have a complexity of O(N logN), where N = max{n;m} is the maximum of n and m, i.e., N is the maximum of the length of the two arrays. If your code ends up having a complexity of O(N2), your work won't be counted. If you write a code having complexity better than O(N logN), such as O(N), you will have to provide a write-up explaining why your code works, and why the complexity is O(N).

Answer 1

Program in java:

//importing required package
import java.util.ArrayList;
import java.util.List;
//class declaration
public class CommonElement {
    //main method
    public static void main(String[] args) {
        //initiallizing the arrays
        int A[] = {7,13, 19, 20, 22, 22, 37, 37};
        int B[] = {7, 14, 17, 22, 28, 31, 37, 37, 37, 43};
        //calling function to obtain the common element
        numCommonElements(A, B, A.length, B.length);
    }
    //method to find the common element
    private static int numCommonElements(int A[], int B[], int lenA, int lenB) {
        // creating list to store the common elements
        List<Integer> number=new ArrayList<>();
        //variable declaration
        int element;
        boolean flag;
        //running the loop to find the common number
        for(int i=0;i<lenA;i++){
            //calling binary search to obtain common element
            element=binSearch(B, 0, lenB, A[i]);
            //if the value of the element is not equal to -1 means the element is common to both arrays
            if(element!=-1){
                flag=true;
                //searching in the array list if the number is already present, if not add the common element
                for(int j=0;j<number.size();j++){
                    if(element==number.get(j)){
                        flag=false;
                        break;
                    }
                }
                //adding common element to the common element list
                if(flag!=false){
                    number.add(element);
                    flag=true;
                }
              
            }
        }
        //printing the common element
        System.out.println(number);
        //printing the count of common element
        System.out.println(number.size());
        return 0;
    }
    private static int binSearch(int ar[], int left, int right, int num)
    {
        if (right >= left) {
            int middle = left + (right - left) / 2;

            // If the element is present at the
            // middle itself
            if (ar[middle] == num)
                return num;

            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (ar[middle] > num)
                return binSearch(ar, left, middle - 1, num);

            // Else the element can only be present
            // in right subarray
            return binSearch(ar, middle + 1, right, num);
        }

        // We reach here when element is not present
        // in array
        return -1;
    }
}

Output: