Finding an elements within a range using O(n) runtime

Question

I am trying to write a function the receives an array with size "N" from the user, with values between 0--->N-1 the function should return "1" if all the values between 0---->N-1 are there otherwise it returns 0. we can assume that the numbers that user will input are only valid values. between 0---->N-1.

Example: N=5,Values: 2,1,4,0,3---->returns 1, N=5,values: 2,3,4,0,3---->returns 0

I tried various ways to solve this problem.

thought about a factorial, but find that there are many ways to get the same factorial using duplicate numbers and unique numbers. also thought about sum the numbers, but still too many ways to get the same answer. Is there any way, to be sure I have only unique items without subarray?

WE CANT USE SUBARRAY(another counter array etc.), AND THE FUNCTION SHOULD RUN O(n).

Answer 1

If you're allowed to modify the input array, the problem can be solved in O(N).

Observations:

1. If the array was sorted, the problem would be trivial.

2. Sorting an array 0...N-1 where values are also 0...N-1 is also trivial, since each element's position is its value, you can iterate once, swapping elements into their final position.

Just need an additional check during swapping that the element at position i doesn't already have the value i, which would mean i appears twice in the array.

int check(unsigned* a, unsigned size) {
    for (unsigned i = 0; i < size; ++i) {
        unsigned b = a[i];
        if (b != i) {
            do {
                if (b < 0 || b >= size)
                    return false; // value out of range
                unsigned c = a[b];
                if (b == c)
                    return false; // duplicate value
                a[b] = b;
                b = c;
            } while (b != i);
            a[i] = i;
        }
    }
    return true;
}

Note that the the inner loop makes the solution look O(N²), but it's not - each element is visited at most twice. The inner loop is needed to resolve cycles as in {1,2,3,0}.