# PermCheck Codility

The following code gets 100% on the PermCheck task on Codility. It should be O(N).

The question is:

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:

function solution(A);


that, given an 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].

Let me know if you think it can be improved, but I think it is pretty good. ;)

function solution(A) {
let m = A.length;
let sumA = A.reduce((partial_sum, a) => partial_sum + a);
let B = Array.apply(null, Array(m)).map(function () {});
var sum_indices = 0;
for (var i = 0; i < m; i++) {
B[A[i] - 1] = true;
sum_indices += i + 1;
}
if (sum_indices == sumA && B.indexOf(undefined) == -1) {
return 1;
} else {
return 0;
}
}


Summing the arrays is not necessary. You only need to check that the input's maximum and length are equal, and that it's free of duplicates.

This approach scores 100% as well. It saves a couple of array traversals and exits earlier when a duplicate exists.

function solution(A) {
var max = 0,
seen = Array( A.length );
for (var i of A) {
if (i>max) max=i;
if (seen[i]) return 0;
seen[i]=true;
}
return +(max == A.length);
}

• Good solution though I would consider a map or set instead of array for your seen variable, as intent would probably be a little clearer. – Mike Brant Mar 5 '19 at 3:27
• @MikeBrant I tried it before posting, but arrays of integers (or booleans) are very hard to beat, performance-wise. Using a set was about 4x slower. That said, it does make the code tidier. See Blindman67's solution for a good example. – Oh My Goodness Mar 5 '19 at 16:10

You can use a Set to reduce the mean complexity.

There are also several opportunities to exit the function early.

• When a duplicate is found
• When a value is found greater than the array length

Thus we get...

function solution(A) {
const found = new Set();
for (const num of A) {
if (found.has(num) || num > A.length) { return 0 }

• I think your final conditional is not even needed and you can just return 1 after the loop exits. – Oh My Goodness Mar 5 '19 at 13:02
• if (len > 1e5) { return 0 } is redundant, given the assumptions – André Werlang Mar 9 '19 at 0:11
• @AndréWerlang Ah yes I see N is the max array length, not the max valid sequence size. No point holding length in len so almost nothing left of the function. – Blindman67 Mar 9 '19 at 1:55