### Problem

Source: Codility

Given an array `A`

of length `n`

filled with integers find the smallest missing positive number.

#### Example:

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

[1,2] =>3

#### Restrictions

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

### My Solution

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. ðŸ¤·

## 0 Comments

## Leave a comment