Find the Union and Intersection of the two sorted arrays in C++
Union and Interaction of the two sorted arrays in C++
Here, in this page we will discuss the program to find the union and interaction of two sorted arrays in C++ . We are given with two sorted arrays and we have to find the union and interaction of the given two arrays.
Algorithm to find Union :
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
- If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
- If both are same then print any of them and increment both i and j.
- Print remaining elements of the larger array.
Algorithm to find Interaction :
- Use two index variables i and j, initial values i = 0, j = 0.
- If arr1[i] is smaller than arr2[j] then increment i.
- If arr1[i] is greater than arr2[j] then increment j.
- If both are same then print any of them and increment both i and j.
Code to find Union and Interaction of the two sorted arrays in C++
#include <bits/stdc++.h>
using namespace std;
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void printUnion(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
cout << arr1[i++] << " ";
else if (arr2[j] < arr1[i])
cout << arr2[j++] << " ";
else {
cout << arr2[j++] << " ";
i++;
}
}
/* Print remaining elements of the larger array */
while (i < m)
cout << arr1[i++] << " ";
while (j < n)
cout << arr2[j++] << " ";
}
void printIntersection(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] */
{
cout << arr2[j] << " ";
i++;
j++;
}
}
}
/* Driver program to test above function */
int main()
{
int m, n;
cin>>m;
int arr1[m];
for(int i=0; i<m; i++)
cin>>arr1[i];
cin>>n;
int arr2[n];
for(int i=0; i<n; i++) cin>>arr2[i];
// Function calling
cout<<"Union : ";
printUnion(arr1, arr2, m, n);
cout<<"\nInteraction ";
printIntersection(arr1, arr2, m, n);
return 0;
}
Output
5
1 2 3 4 5
4
1 2 3 4
Union : 1 2 3 4 5
Intersection : 1 2 3 4
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Login/Signup to comment