Union and Intersection of two sorted arrays

Union and Intersection of two sorted arrays

Union of arrays arr1[] and arr2[]

// C program to find union of

// two sorted arrays

#include<stdio.h>

/* Function prints union of arr1[] and arr2[]

   m is the number of elements in arr1[]

   n is the number of elements in arr2[] */

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++]);

}

/* Driver program to test above function */

int main()

{

  int arr1[] = {1, 2, 4, 5, 6};

  int arr2[] = {2, 3, 5, 7};

  int m = sizeof(arr1)/sizeof(arr1[0]);

  int n = sizeof(arr2)/sizeof(arr2[0]);

  printUnion(arr1, arr2, m, n);

  getchar();

  return 0;

}

Output:

1 2 3 4 5 6 7

Intersection of arrays arr1[] and arr2[]

// C program to find intersection of

// two sorted arrays

#include<stdio.h>

/* Function prints Intersection of arr1[] and arr2[]

   m is the number of elements in arr1[]

   n is the number of elements in arr2[] */

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++;

    }

  }

}

/* Driver program to test above function */

int main()

{

  int arr1[] = {1, 2, 4, 5, 6};

  int arr2[] = {2, 3, 5, 7};

  int m = sizeof(arr1)/sizeof(arr1[0]);

  int n = sizeof(arr2)/sizeof(arr2[0]);

  printIntersection(arr1, arr2, m, n);

  getchar();

  return 0;

}

Output:

2 5

Example:

Input : arr1[] = {1, 3, 4, 5, 7}

        arr2[] = {2, 3, 5, 6}

Output : Union : {1, 2, 3, 4, 5, 6, 7}

         Intersection : {3, 5}

Input : arr1[] = {2, 5, 6}

        arr2[] = {4, 6, 8, 10}

Output : Union : {2, 4, 5, 6, 8, 10}

         Intersection : {6}