CODEWITHSUNDEEP
carrays
Cocoboom
Cocoboom

Reputation: 35

A function that returns 0 or 1 if all elements in the range 0 to n-1 exist in the array, run time O(n)

EDIT: I forgot to mention that I do not want to allocate another temporarily array.

I am trying to solve a problem in C, which is: Suppose you were given an array a and it's size N. You know that all of the elements in the array are between 0 to n-1. The function is supposed to return 0 if there is a missing number in the range (0 to n-1). Otherwise, it returns 1. As you can understand, duplicates are possible. The thing is that its supposed to run on O(n) runtime. I think I managed to do it but i'm not sure. From looking at older posts here, it seems almost impossible and the algorithm seems much more complicated then the algorithm I have. Therefore, something feels wrong to me. I could not find an input that returns the wrong output yet thou.

In any case, I'd appreciate your feedback- or if you can think of an input that this might not work for. Here's the code:

int missingVal(int* a, int size)
{
  int i, zero = 0;
  for (i = 0; i < size; i++)
    //We multiply the element of corresponding index by -1
    a[abs(a[i])] *= -1;

  for (i = 0; i < size; i++)
  {
     //If the element inside the corresponding index is positive it means it never got multiplied by -1 
     //hence doesn't exist in the array
     if (a[i] > 0)
       return 0;

     //to handle the cases for zeros, we will count them
     if (a[i] == 0)
       zero++;
  }
  if (zero != 1)
    return 0;

  return 1;
}

Upvotes: 0

Views: 765

Answers (4)

Bob__
Bob__

Reputation: 12749

To overcome the requirement that excludes any extra memory consumption, the posted algorithm changes the values inside the array by simply negating their value, but that would leave index 0 unchanged.

I propose a different mapping: from [0, size) to (-1 - size, -1], so that e.g. {0, 1, 2, 3, 4, ...} becomes {-1, -2, -3, -4, -5, ...}. Note that, for a two's complement representation of integers, INT_MIN = -INT_MAX - 1.

//  The following assumes that every value inside the array is in [0, size-1)
int missingVal(int* a, int size)      // OT: I find the name misleading
{
    int i = 0;
    for (; i < size; i++)
    {
        int *pos = a[i] < 0
            ? a + (-a[i] - 1)  // A value can already have been changed...
            : a + a[i];

        if ( *pos < 0 )        // but if the pointed one is negative, there's a duplicate
            break;

        *pos = -1 - *pos;
    }

    return i == size;         // Returns 1 if there are no duplicates 
}

If needed, the original values could be restored, before returning, with a simple loop

if ( i != size ) {
    for (int j = 0; j < size; ++j) {
        if ( a[j] < 0 )
            a[j] = -a[j] - 1;
    }
} else {                             // I already know that ALL the values are changed
    for (int j = 0; j < size; ++j)
        a[j] = -a[j] - 1;
}

Upvotes: 0

molamk
molamk

Reputation: 4116

This problem is the same as finding out if your array has duplicates. Here's why

  1. All the numbers in the array are between 0 and n-1
  2. The array has a size of n

If there's a missing number in that range, that can only mean that another number took its place. Which means that the array must have a duplicate number

An algorithm in O(n) time & O(1) space

  1. Iterate through your array
  2. If the sign of the current number is positive, then make it negative
  3. If you found a negative this means that you have a duplicate. Since all items are originally greater (or equal) than 0

Implementation

int missingVal(int arr[], int size)
{
    // Increment all the numbers to avoid an array with only 0s
    for (int i = 0; i < size; i++) arr[i]++;

    for (int i = 0; i < size; i++)
    {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] = -arr[abs(arr[i])];
        else
            return 0;
    }

    return 1;
}

Edit

As Bruno mentioned if we have an array with all zeros, we could have run into a problem. This is why I included in this edit an incrementation of all the numbers.

While this add another "pass" into the algorithm, the solution is still in O(n) time & O(1) space

Edit #2

Another great suggestion from Bruno which optimizes this, is to look if there's more than one zero instead of incrementing the array.

If there's 2 or more, we can directly return 0 since we have found a duplicate (and by the same token that not all the numbers in the range are in the array)

Upvotes: 2

bruno
bruno

Reputation: 32586

your program works and it is in O(N), but it is quite complicated and worst it modify the initial array

can be just that :

int check(int* a, int size)
{
  int * b = calloc(size, sizeof(int));
  int i;

  for (i = 0; i != size; ++i) {
    b[a[i]] = 1;
  }

  for (i = 0; i != size; ++i) {
    if (b[i] == 0) {
      free(b);
      return 0;
    }
  }

  free(b);
  return 1;
}

Upvotes: 2

john elemans
john elemans

Reputation: 2676

Just copy the values to another array placing each value in its ordinal position. Then walk the copy to see if anything is missing.

Upvotes: 2

Related Questions