# Code Corner: Permutation Check

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 on Twitter.