Saturday, September 21, 2019

C++: Find common elements in three sorted arrays.

We are given three sorted arrays and we need to find the elements that are common to the three arrays.

#include <iostream>
using namespace std;
bool binarySearch(int arr[], int l, int r, int key) {
if(l>r)
return false;
int mid = l + (r-l)/2;
if(arr[mid] == key)
return true;
if(key < arr[mid])
return binarySearch(arr, l, mid-1, key);
return binarySearch(arr, mid+1, r, key);
}
void findCommon(int ar1[], int ar2[], int ar3[], int n1, int n2, int n3) {
for(int i = 0; i<n1; i++) {
if(binarySearch(ar1, 0, n1-1, ar1[i])
&& binarySearch(ar2, 0, n2-1, ar1[i])
&& binarySearch(ar3, 0, n3-1, ar1[i]))
cout<<ar1[i]<<" ";
}
}
int main()
{
int ar1[] = {1, 5, 10, 20, 40, 80};
int ar2[] = {6, 7, 20, 80, 100};
int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};
int n1 = sizeof(ar1)/sizeof(ar1[0]);
int n2 = sizeof(ar2)/sizeof(ar2[0]);
int n3 = sizeof(ar3)/sizeof(ar3[0]);
cout << "Common Elements are ";
findCommon(ar1, ar2, ar3, n1, n2, n3);
return 0;
}
Output: 20 80

Here we use binary search to check if the element is present in the array or not. We iterate only the first array and check if each element in the first array is present in other two arrays. The function 'binarySearch()' returns 'true' if the element is found in any of the array and at last if all the three arrays does contain the element, then that element is printed.

No comments:

Post a Comment