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

• wildplasser: If an element is missing, what will be the size of the array?
• Barmar: @EugeneSh. I don't think that works. {3, 0, 0} will produce the same sum as {0, 1, 2}
• Eugene Sh.: Ah, I think I misunderstood the question. Sorry for the confusion
• klutt: "Most efficient"? In respect to what? This does not really seem to be a problem that needs optimizing.
• Tiran: @klutt its one of the problems we have for an assignment, and we have to figure out for each one the best efficiency

Answer 1

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.

• Tyler: Are we guaranteed that the array only contains values within [0 - n-1]? The function could be given an array {0,1,3} which should return false but would go out of bounds with this solution. Although you could then just fail instantly if a higher value is found
• kaylum: @Tyler Good point. Though that could be checked for with an extra if condition without increasing the order of complexity.
• chux: Tiran, the algorithm is sound O(n) yet needs some refinement on start-up, ending and jumping yourself. The task looks too fun to hand you working code - enjoy.
• Tiran: sorry i dont think i fully understand this solution
• Ctx: This method employs a double-use of the existing array to avoid a second array and hence works with no additional space requirement. Good idea!

Answer 2

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