Find the Union and Intersection of the two sorted arrays.

Given two arrays A and B of size N and M respectively. The task is to find union between these two arrays.

Union of the two arrays can be defined as the set containing distinct elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in unio

Constraints:
1 ≤ N, M ≤ 105
1 ≤ A[i], B[i] < 105

Expected Time Complexity : O((n+m)log(n+m))
Expected Auxilliary Space : O(n+m)

//Here we have a full program to print union of A and B

1:  #include <bits/stdc++.h>   
2:  using namespace std;   
3:  int printUnion(int arr1[], int arr2[], int m, int n)   
4:  {   
5:    int i = 0, j = 0;   
6:    while (i < m && j < n) {   
7:      if (arr1[i] < arr2[j])   
8:        cout << arr1[i++] << " ";   
9:      else if (arr2[j] < arr1[i])   
10:        cout << arr2[j++] << " ";   
11:      else {   
12:        cout << arr2[j++] << " ";   
13:        i++;   
14:      }   
15:    }   
16:    /* Print remaining elements of the larger array */  
17:    while (i < m)   
18:      cout << arr1[i++] << " ";   
19:    while (j < n)   
20:      cout << arr2[j++] << " ";   
21:  }   
22:  /* Driver program to test above function */  
23:  int main()   
24:  {   
25:    int arr1[] = { 1, 2, 4, 5, 6 };   
26:    int arr2[] = { 2, 3, 5, 7 };   
27:    int m = sizeof(arr1) / sizeof(arr1[0]);   
28:    int n = sizeof(arr2) / sizeof(arr2[0]);   
29:    // Function calling   
30:    printUnion(arr1, arr2, m, n);   
31:    return 0;   
32:  }   

//Here we have an stl function which return the number of elements in A union B

 

1:  int doUnion(int a[], int n, int b[], int m)   
2:  {  
3:   set<int> s;  
4:   for(int i=0;i<n;i++)  
5:   {  
6:     s.insert(a[i]);  
7:   }  
8:   for(int i=0;i<m;i++)  
9:   {  
10:     s.insert(b[i]);  
11:   }  
12:   return s.size();  
13:  }