Source: Codility

Given an array `A`

of length `n`

filled with integers find the smallest missing positive number.

[4,8,1,3,2] => 5

[1,2] =>3

- n ranges from 1 .. 100,000
- Values of A range from -1,000,000 to 1,000,000

As usual, I decided to first take a brute force approach. As a result, I forced the array into a Set then iteratively checked each number sequentially from 1 to n+1.

functionbrute_force(A) {constaSet =newSet(A)for(leti = 1; i <= aSet.size + 1; i++) { if (!aSet.has(i)) {returni } } }

This worked well. The next task was to think about how to make it work faster. The worst-case scenario would be all positive natural numbers from 1 to n with no missing numbers since we’d have to check every number.

I thought we could possibly squeeze a few milliseconds by `reducing`

A to a positive only `set`

but honestly, the constructor is plenty fast so there was no visible benefit. In the end, I didn’t find another way to get this to go faster so I decided to see how the brute-force method faired.

Turns out, very well. It passed all performance tests with flying colors. So I guess that’s that. 🤷

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.