C28 Answer

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

/* Puzzle C28 -- check if all the integers 0..N-1 are in an array.
|  Return the first integer not found, or -1 if all integers are
|  present.
*/
int fullArrayCheck( int arr[], int size )
{
  int target, j;
  
  for ( target=0; target < size; target++ )
  {
    j = 0;
    while ( j < size && arr[j] != target ) j++ ;

    if ( j == size ) return target;
  }
  
  return -1;
}

void fillArrayInOrder( int arr[], int size, int first )
{
  int j;

  for ( j=0; j < size; j++ )
  {
    arr[j] = first+j;
  }
}

void printArray( int arr[], int size )
{
  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] );    
  }
}

#define SIZE 50
int main(int argc, char *argv[])
{
  int x[SIZE] ;
  int target ;
  fillArrayInOrder( x, SIZE, 0 );
  x[ 32 ] = 99 ;
  printArray( x, SIZE );
  printf("\n");

  if ( (target = fullArrayCheck( x, SIZE )) == -1 )
    printf("All elements present\n");
  else
    printf("Element %d missing\n", target);

  system("PAUSE");	
  return 0;
}

Comments: The function contains a loop within a loop, and both loops potentially iterate N times. So the worst case running time is O(N²). This is bad. However, if there are many missing elements, the usual running time is much better than this.

In some circumstances it might be sensible to sort the array first using a N log N sort, and then make one pass over the sorted array, checking for 0, 1, 2, 3, ... But possibly the order of elements in the array is important, and should not be changed. So, perhaps, you could sort and check a copy of the array. But this had disadvantages too, especially if you use dynamic memory for the array copy.