Puzzle DE44

Fill a third array with the elements two unsorted arrays have in common

[H-20] Write a function that looks at two arrays and fills a third array with the elements that are common to the first two arrays. The third array has only one copy of each element in common with the other two arrays. The first two arrays may be of unequal sizes. Assume that the arrays are not in sorted order. Return the number of elements placed in the third array. Assume that the third array already exists and is long enough to hold all the common values. Here are some sample runs:

Array A:
  17    1    3   19    3    7    9   13   15    2

Array B:
   2    3    6    8    9    3    5   16

Elements in Common:
   3    9    2
   
   
Array A:
   3    3    5    8    8    9    7    0   -1   -2
   1    1
Array B:
   3    3    3    3    3    5    5    5

Elements in Common:
   3    5

This puzzle can be solved with a function that takes O(n²) time in the worst case. This would be OK to use only for fairly small arrays. A better solution would use an O(n·logn) sorting method first.

Here is a testing framework:

/* Puzzle D44 -- fill a third array with the elements
|                two other arrays have in common
|
|  Write function that looks at two arrays and fills a
|  third array with the elements that are common to the
|  first two arrays. The third array has only one copy
|  of each element in common with the other two arrays.
|  The first two arrays may be of unequal sizes.
|  Return the number of elements in the third array.
|
*/
int commonElements( int arrA[], int sizeA,
                    int arrB[], int sizeB,
                    int out[],  int sizeOut )
{
}

void printArray( int size, int arr[] )
{
  const int N = 10;
  int j;
  
  for ( j=0; j<size; j++ )
  {
    if ( j%N == N-1 )
      printf("%4d\n", arr[j] );
    else
      printf("%4d ", arr[j] );    
  }
}

int main()
{
  int count ;
  
  int arrA[] = { 3, 3, 5, 8, 8, 9, 7, 0, -1, -2, 1, 1 };
  int arrB[] = { 3, 3, 3, 3, 3, 5, 5, 5, 5, 5 };

  int sizeA = sizeof( arrA )/sizeof( int );
  int sizeB = sizeof( arrB )/sizeof( int );

  int arrC[sizeA+sizeB];
 
  printf("Array A:\n");
  printArray( sizeA, arrA );
  printf("\nArray B:\n");
  printArray( sizeB, arrB );

  count = commonElements( arrA, sizeA, arrB, sizeB, arrC, sizeA+sizeB );
  
  printf("\n\nElements in Common:\n");
  printArray( arrC, count );
  
  printf("\n\n");
  return 0;
}