Array check for all integers from 0 to size-1

Question

Here's the question: My program gets an array of the size n, that contains numbers from 0 to n-1. You can assume that we don't get numbers below 0 or numbers above n-1.

I need to check if the array contains ALL the numbers between 0 to n-1, and return 1 if it does. 0 otherwise.

You are not allowed to use another array, and the program must run in O(n).

examples:

Array of the size 5: 4,1,0,3,2 return 1.

Array of the size 5: 4,1,0,3,1 return 0 (2 isn't in the array)

Tried in servral ways got stuck any help will be appreciated.

Here is a hint: What do you get if you sum all the values when all values you need exist? — Hogan, Jan 04 '16 at 21:17
if i sum all values i can get false postive for some arrays same for multiplication all values.. — barmash, Jan 04 '16 at 21:25
Walk the array, using the value in each array element to negate-1 that element. `a[0] --> 5` then `a[5] = -1 - a[5]`. If an element is all ready marked, fail. This works as long as the array has 1 bit available for marking/element. Code can also restore the array. — chux - Reinstate Monica, Jan 04 '16 at 21:32
@chux: I deleted that comment, because I overlooked you mark a different entry. I still wonder how that works. If you make that an answer, could you elaborate? — too honest for this site, Jan 04 '16 at 21:38
Would [in-place radix sort](http://stackoverflow.com/q/463105/2304215) help? — chrk, Jan 04 '16 at 21:40
@Olaf See below answer. OTOH, I suspect there is a way to walk the array, using the value in each element to get to the next element. One needs to detect loops. A repeat would indicate a non-unique list. Yet I have not figured out this algorithm yet. — chux - Reinstate Monica, Jan 04 '16 at 22:02
chux's solution should definitely work, although it leaves the values in the array changed (but this could be reversed in a post-pass). Perhaps a nicer solution would be to do an in-place O(n) sort on the values, although this would of course leave the array permanently changed (but it would contain the original values in sorted order). — Tom Karzes, Jan 04 '16 at 22:06
@chux : re `walk the array, […] detect loops`: 3,2,1 - you can detect the cycle (3,1), but how do you get an index not visited yet? — greybeard, Jan 04 '16 at 22:47
@greybeard To be clear, I have 2 solutions, one [commented](http://stackoverflow.com/questions/34599945/array-check-for-all-integers-from-0-to-size-1?noredirect=1#comment56946070_34599945) and [posted](http://stackoverflow.com/a/34600583/2410359) and the [2nd one](http://stackoverflow.com/questions/34599945/array-check-for-all-integers-from-0-to-size-1?noredirect=1#comment56946910_34599945) just mused about. Of the 2nd one I have not solved it yet. The first one is not stymied by loops. — chux - Reinstate Monica, Jan 04 '16 at 22:51

score 3 · Answer 1 · answered Jan 04 '16 at 21:55

3

Let us assume 2's complement int, and the array can be changed. Use the sign bit to mark cells visited.

Lightly tested code

int OneOfEach(int *A, int count) {
  int result = 1;
  for (int i = 0; i < count; i++) {
    int cell_to_mark = A[i];
    if (cell_to_mark < 0) {
      cell_to_mark = -1 - cell_to_mark;
    }
    assert(cell_to_mark >= 0 && cell_to_mark < count);
    if (A[cell_to_mark] < 0) {
      // done all ready
      result = 0;
      break;
    }
    A[cell_to_mark] = -1 - A[cell_to_mark];
  }
  // restore.
  for (int i = 0; i < count; i++) {
    if (A[i] < 0) {
      A[i] = -1 - A[i];
    }
  }
  return result;
}

answered Jan 04 '16 at 21:55

chux - Reinstate Monica

143,097
13
135
256

Note that, on a two's complement system, `-1 - x` is just `~x`. – Tom Karzes Jan 04 '16 at 22:22
1

@Tom Karzes True about `-1 - x` is just `~x`. I tend to only code bit operators `~ & | ^ >> <<` with unsigned types. Get in less trouble that way. – chux - Reinstate Monica Jan 04 '16 at 22:43
@chux You would have a bad time with Java ;) – Juan Lopes Jan 04 '16 at 23:37
1

@JuanLopes: In a world of tea drinkers who needs Java? – too honest for this site Jan 05 '16 at 07:53

rcgldr · Answer 2 · 2016-01-05T14:58:32.770

This can be done with something similar to special cycle sort for values 0 to n-1. Time complexity is O(n).

/* check if a[] has one each of numbers 0 to n-1 */
/* reorder a[] in place according to values in a[] */
/* a[] only has numbers 0 to n-1 */
/* also sorts array in O(n) time */
int chka(int a[], int n)
{
int i, j, k;
    for(i = 0; i < n; i++){
        if(i != a[i]){                  /* if element out of place */
            k = i;                      /*  cycle elements */
            while(i != (j = a[k])){
                if(a[k] == k)           /*  if destination already has */
                    return 0;           /*    value, it's a duplicate */
                a[k] = k;
                k = j;
                if(k < 0 || k >= n)     /*  if out of range */
                    return 0;           /*    return 0 */
            }
            if(a[k] == k)               /*  if destination already has */
                return 0;               /*    value, it's a duplicate */
            a[k] = k;
        }
    }
    return 1;
}

score 1 · Answer 3 · answered Jan 05 '16 at 03:10

You just put each element where it belongs in order. If there are two that belong in the same spot, then you have a duplicate, which means one must be missing.

bool checkArray(int *array, int count)
{
    int i=0;
    while (i<count)
    {
        int el = array[i];
        if (el < 0 || el >=count)
            return false;
        if (el == i)
        {
           //already in the right place
           ++i;
           continue;
        }
        if (array[el]==el)
            return false; //duplicate
        //swap element into correct position
        array[i]=array[el];
        array[el]=el;
        //loop to reprocess the same position, since we just
        //changed the element there
    }
    return true;
}

Array check for all integers from 0 to size-1

3 Answers3