Say the arrays are labled ‘A’ and ‘B’. Just two pointers ‘a’ and ‘b’ (pointing in their respective arrays). Without loss of generality, say that ‘B’ starts with a larger element. Keep on advancing ‘a’ until *a < *b is no longer true. As these arrays are sorted, these values must be unique to A. Now advance ‘b’ in a similar manner. In the case where *a == *b, advance both pointers. Don’t output the element as it exists in both.
Alternately, add all elements of A into a hashtable. Now iterate through B outputting all elements that are not in the hashtable.
Both algorithms have the same asympotic complexity but the first doesn’t require any extra memory and should run a bit faster.
Here is algorithm 1
#include <stdio.h>
#include <stdlib.h>
void mydiff(int * arr1, int * end1, int * arr2, int * end2, int * diff1, int* diff2);
int main() {
int arr1] = {2, 4, 5, 6, 7, 8, 20, 33, 34, 56};
int arr2] = {1, 2, 6, 7, 8, 10, 11, 45, 98};
int * diff1 = calloc(sizeof(int), 10);
int * diff2 = calloc(sizeof(int), 9);
mydiff(arr1, arr1 + 10, arr2, arr2 + 9, diff1, diff2);
printf("diff in arr1:
");
while(*diff1) {
printf("%d ", *diff1);
diff1++;
}
printf("
diff in arr2:
");
while(*diff2) {
printf("%d ", *diff2);
diff2++;
}
}
void getTail(int * arr, int * end, int * diff) {
while(arr != end) {
*diff = *arr;
diff++;
arr++;
}
}
void mydiff(int * arr1, int * end1, int * arr2, int * end2, int * diff1, int * diff2) {
if(arr1 == end1) {
getTail(arr2, end2, diff2);
return;
}
if(arr2 == end2) {
getTail(arr1, end1, diff1);
return;
}
while(*arr1 < *arr2 && arr1 != end1) {
*diff1 = *arr1;
diff1++;
arr1++;
}
while(*arr2 < *arr1 && arr2 != end2) {
*diff2 = *arr2;
diff2++;
arr2++;
}
if(*arr1 == *arr2) {
if(arr1 != end1)
arr1++;
if(arr2 != end2)
arr2++;
}
mydiff(arr1, end1, arr2, end2, diff1, diff2);
}