Puzzle DE42

Find the first element of one array that is not in another

[M-7] Write a function that has four arguments: two integer arrays, and their sizes. The arrays may be of different sizes. The function returns the index of the first value in the first array that is not somewhere in the second array. If all values in the first array are also in the second array, return -1.

The values in the arrays need not be in order. Values in the arrays may be repeated. Each instance of a repeated value can match the same element in the second array. Here is are several sample runs of a testing program:

Array A:
   2    2    3    3    7    1   29   19    2   19
   5
Array B:
  29   19    5    3    7    2
Value 1 is in A but not in B

The program returned index 5, which is the index of the element 1 in the first array.

Array A:
   2    2    3    3    7    5   29   19    2   19
   5
Array B:
  29   19    5    3    7    2
All elements in A are found in B

The program returned index -1, because every element in A can be found somewhere in B. Notice that the elements do not need to be paired one to one: it is enough for B to have a single 2 to match the several 2s in A.

Array A:
   2    2    3    3    7    5   29   19    2   19
   5
Array B:
  29   19   99    3    7    2
Value 5 is in A but not in B:

Here is a testing framework:

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

/* Puzzle D42 -- find the first element of one array that is not in another
|
|  The function returns the index of the first
|  element of the first array that is not also in the second array.
|  If all elements of the first array are also in the second array,
|  return -1.
*/
int allPresent( int sizeA, int arrA[], int sizeB, int arrB[] )
{
}

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

  /* Edit the values in these arrays to test your function */   
  int arrA[] = { 2, 2, 3, 3, 7, 1, 29, 19, 2, 19, 5, 44 };
  int arrB[] = { 1, 29, 19, 5, 3, 2, 7, 2, 1 };
  
  int sizeA = sizeof( arrA )/sizeof( int );
  int sizeB = sizeof( arrB )/sizeof( int );
 
  printf("Array A:\n");
  printArray( sizeA, arrA );
  printf("\nArray B:\n");
  printArray( sizeB, arrB );

  if ( (loc=allPresent( sizeA, arrA, sizeB, arrB )) != -1 )
    printf("\nValue %d is in A but not in B: \n", arrA[loc]);
  else
    printf("\nAll elements in A are found in B:\n");

  printf("\n\n");
  return 0;
}