Answer DE44

#include <stdio.h>
#include <stdlib.h>

/* 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 )
{
  int eleA, eleB, eleC;
  int ixa,  ixb,  ixc;
  int countOut = 0;
  int foundB, foundOut;
  
  /* look sequentially at elements in arrA */
  for ( ixa=0; ixa<sizeA; ixa++ )
  {
    eleA = arrA[ixa];
    
    /* check if eleA is also in arrB */
    foundB = 0;
    for ( ixb=0; ixb<sizeB && !foundB; ixb++ )
    {
      if ( eleA==arrB[ixb] ) foundB = 1;
    }
    
    /* add it to out if it is not already there */
    if ( foundB )
    {
      foundOut = 0;
      for ( ixc=0; ixc<countOut && !foundOut; ixc++ )
        if ( eleA==out[ixc] ) foundOut = 1;
        
      if ( !foundOut && countOut < sizeOut )
      {
        out[countOut] = eleA;
        countOut++ ;
      }
      
    }
  }
  return countOut ;
}

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

Comments: Say that both arrays are N elements long. Then the best case for this function is if the first array contains only N instances of the same value x, and this value is the first one in the second array. Then the first array is inspected in N iterations, and each iteration does a fixed amount of work with the other two arrays. So the best case is O(N).

The worst case (for both arrays N elements long) is if the arrays have no elements in common. Then each iteration over the first array requires a search through the the N elements of the second array, for O(N²) operations total.

Another case (for both arrays N elements long) is if the two arrays have N elements in common, so that the output array will grow to be N elements long. Now the N elements of the first array are inspected. For each of these elements, it takes (on the average) N/2 iterations through the second array to find the matching element, and (on the average) N/2 iterations through the output array to check for duplicates. So this also is a total of O(N²) operations.

The input arrays could be sorted first, at a cost of N·log N, each. A single pass through the sorted arrays can produce the output array, at a cost of N. The total cost for this approach is 2·N·log N + N, which is O( N·log N ).

If the arrays are expected to be more than 50 or so elements long, the sort-first approach should be used.