Problem
Find Union and Intersection of two sorted arrays
Example
For example, if the input arrays are:arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}.
Solution
Algorithm Union(arr1[], arr2[]):For union of two arrays, follow the following merge procedure.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
3) If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
4) If both are same then print any of them and increment both i and j.
5) Print remaining elements of the larger array.
#include<stdio.h> #include<stdio.h> int printUnion(int arr1[], int arr2[], int m, int n) { int i = 0, j = 0; while(i < m && j < n) { if(arr1[i] < arr2[j]) printf(" %d ", arr1[i++]); else if(arr2[j] < arr1[i]) printf(" %d ", arr2[j++]); else { printf(" %d ", arr2[j++]); i++; } } // Print remaining elements of the larger array while(i < m) printf(" %d ", arr1[i++]); while(j < n) printf(" %d ", arr2[j++]); }
Time Complexity: O(m+n)
Algorithm Intersection(arr1[], arr2[]):
For Intersection 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.
#include<stdio.h> int 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] { printf(" %d ", arr2[j++]); i++; } } }
Time Complexity: O(m+n)
References
0 comments:
Post a Comment