The problem: We are doing a permutation check. Given a list ** A** with

**elements and the task is to determine if**

`n`

**A**

is a permutation of natural numbers from **.**

`1 to n`

For example

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

.

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

### 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

functionsolution(A){constexpectedSum = (n * (n+1)) / 2constactualSum = A.reduce((sum, value)=> sum + value, 0)returnactualSum === expectedSum ? 1 : 0 }

This is efficient but has one tiny problem. Testing failed because of arrays like this

. Notice our requirements didn’t say the numbers didn’t repeat, it was a bad assumption on my part.**[1,1,1,7]**

#### Second attempt

My next thought was to convert

into a **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…

functionsolution(A){constaSet =newSet(A)for(leti = 1;i <= A.length; i++) { if(!aSet.has(i)){return0 } }return1 }

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.

functionsolution(A){constaSet =newSet(A)constn = A.lengthconstexpectedSum = (n * (n+1)) / 2constactualSum = Array.from(aSet).reduce((sum, value)=> sum + value, 0)returnactualSum === 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){return0 }

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.

## 0 Comments

## Leave a comment