The problem: We are doing a permutation check. Given a list A with n elements and the task is to determine if A is a permutation of natural numbers from 1 to n.

For example

[4,2,3,1] is a permutation since all element of the list are in the list [1..n] where n=4.

[4,1,2] is not a permutation since the 2 is missing.

Expected output

An efficient function that returns 1 if A is a permutation and 0 otherwise.

Restrictions:

• 1 <= n <= 100000
• Elements of A are in the range [1..1,000,000,000]
• Be efficient

My Solutions

First Attempt

At first glance I figured easy, just check the sum. The sum of natural numbers can be found using a simple formula sum = n(n+1) / 2 so my first attempt

function solution(A){
    const expectedSum = (n * (n+1)) / 2
    const actualSum = A.reduce((sum, value)=> sum + value, 0)
    return actualSum === expectedSum ? 1 : 0
}

This is efficient but has one tiny problem. Testing failed because of arrays like this [1,1,1,7]. Notice our requirements didn’t say the numbers didn’t repeat, it was a bad assumption on my part.

Second attempt

My next thought was to convert A into a set to get rid of any duplicates since if there were any then it wasn’t a permutation. The next step would be to check if all numbers from 1 to n existed in the set and give up as soon as we failed to find one. Something like this…

function solution(A){
    const aSet = new Set(A)
    for(let i = 1;i <= A.length; i++) {
        if(!aSet.has(i)){
            return 0
        }
    }
    return 1
}

But first I decided to test out a thought. What happens if we check the sum of the set against the expected sum? Apparently we find an over sight in the tests that check solutions.

function solution(A){
    const aSet = new Set(A)
    const n = A.length 
    const expectedSum = (n * (n+1)) / 2 
    const actualSum = Array.from(aSet).reduce((sum, value)=> sum + value, 0) 
    return actualSum === expectedSum ? 1 : 0
}

This isn’t supposed to work because of arrays like [1, 2, 1, 7] but to my surprise, it passed all the tests brilliantly.

Go figure.

There is an easy fix for the bug however, just check set size against list size

if (aSet.size !== n){
    return 0
}

That’s all I have for today. If you found this interesting or have a better way why not leave me a comment, or Follow @phoexer on Twitter.