Complexity to find if there is a missing element in an array

Question

I am trying to write a function (in C) that checks if an array has all the elements (between 0 and its "size-1")

For example, if the array's size is 3, it should have {0, 1, 2 } in any order.

The question is: what is the most efficient complexity to do this without an extra array?

The complexity of my attempt, showed below, is (average of nlogn + n). edit: sorry for the miss understanding, any whole number can be an input, which means checking size wont work --> {0, 0, 3}

int check_missing_element(int *a, int n)
{
    int i = 0;

    quicksort(a, 0, n - 1);

    for (i = 0; i < n; i++)
    {
        if (a[i] != i)
            return 0;
    }

    return 1;
}

Answer 1

Here is an implementation of the cycle-chasing algorithm sketched in chux’ answer, along with a test program.

/*  Return 1 iff each integer in 0...n-1 appears exactly once in a[0]...a[n-1].
    Return 0 otherwise.
*/
int check_missing_element(int *a, int n)
{
    //  Reject elements that are out of bounds.
    for (int i = 0; i < n; ++i)
        if (a[i] < 0 || n <= a[i])
            return 0;

    //  Define a value to mark already seen values with.
    static const int AlreadySeen = -1;

    //  Work through the array.
    for (int i = 0; i < n; ++i)

        //  If we already examined this element, ignore it.
        if (a[i] != AlreadySeen)
        {
            /*  Follow the cycle defined by x -> a[x].  If we encounter an
                already seen element before returning to i, report rejection.
                Otherwise, mark each encountered element seen.
            */
            for (int j = a[i]; j != i;)
            {
                int next = a[j];
                if (next == AlreadySeen)
                    return 0;
                a[j] = AlreadySeen;
                j = next;
            }
        }

    //  Every element has been seen once and only once.  Report acceptance.
    return 1;
}


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


//  Define a comparator for sorting int values in ascending order.
static int Comparator(const void *a, const void *b)
{
    int A = * (const int *) a;
    int B = * (const int *) b;
    return
        A < B  ? -1 :
        A == B ?  0 :
                 +1;
}


//  Provide a reference routine for testing check_missing_elements.
static int check_missing_elementReference(int *a, int n)
{
    /*  Sort the elements.  Iff the array contains each value exactly once,
        this results in an array containing 0, 1, 2, 3,... n-1.
    */
    qsort(a, n, sizeof *a, Comparator);

    //  Test the sorted array.
    for (int i = 0; i < n; ++i)
        if (a[i] != i)
            return 0;
    return 1;
}


#define ArrayLimit  7


#define NumberOf(a) (sizeof (a) / sizeof *(a))


/*  Define a structure used to iterator through test values.

    The indices in the Index array will each run from -x to n, inclusive,
    where x is the number of special values (defined below) and n is the array
    size.  The indices will be incremented lexicographically (odometer style).

    For the indices from -x to -1, the associated value will be one of the
    special values.  For the indices from 0 to n, the associated value will
    equal the index.  Note that n is outside the bounds of array values that
    pass the test.  It is included in testing so that rejections based on it
    are tested.
*/
typedef struct 
{
    int Index [ArrayLimit];
    int Values[ArrayLimit];
} Iterator;


//  Define special values to include in testing.
static const int SpecialValues[] = { INT_MIN, -1, INT_MAX };


/*  Define the number of special values as an int, not a size_t, because we use
    its negation and so need a signed type.
*/
#define NumberOfSpecialValues   ((int) NumberOf(SpecialValues))


//  Initialize an iterator.
static void InitializeIterator(Iterator *Iterator, int n)
{
    for (int i = 0; i < n; ++i)
    {
        Iterator->Index [i] = -NumberOfSpecialValues;
        Iterator->Values[i] = SpecialValues[0];
    }
}


/*  Increment an iterator.  Return 0 if we are done (all fields rolled over,
    bringing the iterator back to the initial state) and 1 otherwise.
*/
static int Increment(Iterator *Iterator, int n)
{
    //  Start at the rightmost field.
    int j =n-1;

    while (0 <= j)
    {
        //  If this field has room to increase, increment it.
        if (Iterator->Index[j] < n)
        {
            ++Iterator->Index[j];

            /*  Set the associated value to either a special value or the
                index value, as described above.
            */
            Iterator->Values[j] =
                Iterator->Index[j] < 0
                    ? SpecialValues[Iterator->Index[j] + NumberOfSpecialValues]
                    : Iterator->Index[j];

            //  There is no carry into the next field, so we are done.
            return 1;
        }

        /*  This field rolls over and resets to its initial value.  Then we
            carry into the next field.
        */
        Iterator->Index [j] = -NumberOfSpecialValues;
        Iterator->Values[j] = SpecialValues[0];
        --j;
    }

    //  All fields rolled over, so we are done.
    return 0;
}


//  Print an array.
static void PrintArray(int *a, int n)
{
    printf("[");
    if (0 < n)
        printf("%d", a[0]);
    for (int i = 1; i < n; ++i)
        printf(", %d", a[i]);
    printf("]");
}


int main(void)
{
    //  Test each array size up to the limit.
    for (int n = 1; n <= ArrayLimit; ++n)
    {
        //  Iterator through all array values.
        Iterator i;
        for (InitializeIterator(&i, n); Increment(&i, n);)
        {
            /*  Since the routines destroy the array, copy the array.  Then
                execute the routine and record the return value.
            */
            int Buffer[ArrayLimit];

            //  Reference routine first.
            memcpy(Buffer, i.Values, n * sizeof *Buffer);
            int expected = check_missing_elementReference(Buffer, n);

            //  Subject routine.
            memcpy(Buffer, i.Values, n * sizeof *Buffer);
            int observed = check_missing_element         (Buffer, n);

            //  Test for a bug.
            if (expected != observed)
            {
                printf("Failure:\n");
                printf("\tArray = "); PrintArray(i.Values, n); printf("\n");
                printf("\tExpected %d but observed %d.\n", expected, observed);
                exit(EXIT_FAILURE);
            }
        }
        printf("Array length %d:  Passed.\n", n);
    }
}

Answer 2

Walk the array using the value [0...n-1] of the element as the next element to visit.

As leaving each element, set its value to n. Any visited element with an n has already been visited and so is a failure - unless we have indexed ourselves. Any element with a value outside [0...n-1] is a failure.

After 'n' visits we are done. O(n).

Sort not needed. This does consume the array.