Problem

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2

is a permutation, but array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

    int solution(int A[], int N);

that, given a array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2

the function should return 1.

Given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3

the function should return 0.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Note:

For the permutation above, N = 4. This means that all the numbers in the array can be put in order as follows: 1, 2, 3, 4 (four numbers). The lesson for this problem is Counting Elements. The candidate should expect that the solution to this problem, needs a count array. With this, the highest possible value in a given array should be N. For a permutation, the number of occurrence of each value in the given array has to be 1 (verified in the count array).

In the non-permutation table in the question, it is true that 2 is missing, but since N, the number of elements is 3, it means that 4 is bigger than N = 3, and that is an accompanied permutation error. Some other number, even bigger than 4 could have been in the place of 4. In that case, more than one number would be missing.

Another possibility of error is that, an integer less than N can occur more than once, and/or with some numbers missing, as in the following list:

    1, 1, 1, 4

Here, 1 has occurred three times with 2 and 3 missing. The highest expected number, 4 is still there.

Strategy

The count tables for the first two arrays above are as follows:

The count table for the array {1, 1, 1, 4} is:

Remember that index 0 and its value of 0 is in the two tables, for convenience. Note that in the non-permutation table, the value (number of occurrence) of the index 2, is 0. In the third table, 1 occurs 3 times; 2 occurs 0 time; 3 occurs 0 time; and 4 occurs 1 time.

So, to know if a array is not a permutation, check if there is an integer which is higher than N (4 is higher than 3 for second example above); check if any integer between 1 and N (inclusive) is missing; and check if any integer between 1 and N (inclusive) occurs more than once.

In order to know if any integer is missing or if any integer occurs more than once, a count array is needed. Both of these requirements are just checked, whether all the values in the count array are 1 (if a given value is missing, then its count is 0; if a given value occurs more than once, then it count is not 1, and is greater than 1).

Checking if an integer is greater than N should be done as the given array is scanned to produce the count array. The given array is scanned in N time to produce the count array of m + 1 cells (including index 0). Another complete N scanning should not waste the time complexity just to know if there is a number in the list that is greater than N, in N time.

The given array is scanned in N time to produce the count array, and then the count array is scanned in M time, to make sure all the values are 1. However, since the size (length) of the count array in this case is M = N plus 1 (for the convenience 0), the time complexity for the above algorithm may be given as O(N+N) and not O(N+M), because M is approximately N in this case. The O(N) time to create the count array, initializing everything (element) to zero, is ignored here.

O(N+N) Time Solution

The program is:

#include <stdio.h>

int solution(int A[], int N) {
    int count[N+1];
    //initialize all count elements to 0
    for (int i=0; i < N+1; i++)    //usually not included in time complexity
        count[i] = 0;

    for (int i=0; i < N; i++) {
        if (A[i] > N)    //if any given element is greater than N
            return 0;
        count[A[i]]++;  //i.e. count[A[i]] = count[A[i]] + 1;
    }

    for (int i=1; i <= N; i++) {
        if (count[i] != 1)
            return 0;
    }

    return 1;   //if no error detected
}

int main() 
{ 
    int P[] = {4, 1, 3, 2};
    int N = sizeof(P) / sizeof(P[0]);    //divide size of array by size of one (first) element
    int ret1 = solution(P, N);
    printf("%i\n", ret1);

    int Q[] = {4, 1, 3};
    N = sizeof(Q) / sizeof(Q[0]);    //divide size of array by size of one (first) element
    int ret2 = solution(Q, N);
    printf("%i\n", ret2);

    return 0; 
} 

At app.codility.com/programmers/, the result is given as: O(N) or O(N * log(N)) detected time complexity. The O(N) time to create the count array, initializing everything (element) to zero, is ignored there, as it has been ignored here (in this tutorial).

Conclusion

To know if a array is a permutation, check if each of the elements from 1 to N occurs once in the count array. This means having the count array in O(N) time by the given array, and then checking if each element occurs once in the count array, in M time.

It may also happen that one or more of the integers in the given array, is greater or much greater than N. In this case, finding its index in the count array is impossible, because the maximum index in the count array is M, which in this problem, is N. Any number greater than N can be spotted, while scanning the given array to create the count array.

It may also happen that there are N elements between 1 and N in the given array, but some elements repeat. This is taken care of, by the fact that the solution function checks, if each value from 1 to N occurs only once, in the count array.

The reader should register at app.codility.com/programmers, so that he/she should be testing his/her own code.

The reader may think that the above problem could have been solved by sorting the list in at least N.log(N) time, and then checking to see that all the elements from 1 to N are in the list in N time. This means O(N.log(N) + N) time. However, the best time complexity is O(N+N). N.log(N) is bigger than O(N). So O(N.log(N) + N) takes longer than O(N+N), and its solution should not be chosen.