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. 🤷

Today I am working on a summation problem made to look like building a tower out of cubic bricks. It’s fun to brute force sometimes.

Coming back to Rust code after a bit of a hiatus with a simple problem… The Two-sum problem. Finding numbers in an array. Yay, fun.

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.