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

`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]**

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

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

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]**

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.

King Pinn: I Salute You. I’m driving halfway across the country and this song is on repeat. Rest in Peace Tonderai Makoni. You were awesome.

After a few weeks off I’m back to business. This is just an update post detailing plans for the rest of the year.

At last we finally have the great reveal, our mystery project was implementing RSA encryption in rust.

We build the final piece of our mystery project, a function that computes modular exponentiation. Come on in, we have large numbers.

We build another part of the mystery project by creating a function that calculates the modular multiplicative inverse of a number.