Union refers to the set of all the elements of the 2 arrays. Intersection here refers to the set of elements which are common in both the arrays.
Steps to find union of 2 arrays:
1) i and j, initial values i = 0, j = 0
2) If a1[i] < a2[j] then print a1[i] and increment i.
3) If a1[i] > a2[j] then print a2[j] and increment j.
4) If a1[i]=a2[j] then print a1[i] increment both i and j.
5) Print remaining elements of the larger array.
int find_union(int arr1[], int arr2[], int SIZE1, int SIZE2) { int i = 0, j = 0; while(i < SIZE1 && j < SIZE2) { if(arr1[i] < arr2[j]) printf(" %d ", arr1[i++]); else if(arr2[j] < arr1[i]) printf(" %d ", arr2[j++]); else { printf(" %d ", arr1[i]); i++; j++; } } /* Print remaining elements of the larger array */ while(i < SIZE1) printf(" %d ", arr1[i++]); while(j < SIZE2) printf(" %d ", arr2[j++]); }
Complexity: O(N) N is size of larger array
Steps to find intersection of 2 arrays:
1) i and j, initial values i = 0, j = 0
2) If a1[i] < a2[j] then increment i.
3) If a1[i] > a2[j] then increment j.
4) If a1[i]=a2[j] then print a1[i] increment both i and j.
int find_intersection(int arr1[], int arr2[], int SIZE1, int SIZE2) { int i = 0, j = 0; while(i < SIZE1 && j < SIZE2) { if(arr1[i] < arr2[j]) i++; else if(arr2[j] < arr1[i]) j++; else { printf(" %d ", arr1[i]); i++; j++; } } }
Complexity: O(N), N is size of larger array
these methods will work only when arrays are sorted na??
Yes, Otherwise you will have to sort the arrays.. Use Quick Sort for O(N logN)
Above union code will fail if the input will be like below
Array1 = (1, 3, 4, 5, 7, 8)
Array2 = (2, 3, 5, 16)
Am i right?