# ETOOBUSY đźš€ minimal blogging for the impatient

# PWC080 - Smallest Positive Number

**TL;DR**

Itâ€™s Perl Weekly Challenge time again, now on issue #080 TASK #1.

And by the wayâ€¦ do you know that depending on the time zone you might already start submitting pull requests for the HacktoberfestÂ®?!?

# The challenge

You are given unsorted list of integers @N. Write a script to find out the smallest positive number missing.

# The questions

There are not *too many* questions that can be asked, butâ€¦

- the list contains integers, but the question asks for a numberâ€¦ well, letâ€™s assume that it must be an integer!
- is it correct to assume that the answer to an empty list is
`1`

? - how to deal with invalid inputs?

# The solution

To be honest, nothing clever came to mind. Which is probably good, especially if I put myself in the shoes of someone doing a job interview!

So my plan is pretty boring:

- sort the list
- go through it and find the lowest positive integer thatâ€™s missing from it.

With one *little* twistâ€¦ why sort the *whole* list? Negative integers
donâ€™t really matter, so we will filter them out beforehand.

After much talking, hereâ€™s the core of the solution:

```
1 sub spnb {
2 my @Np = (0, sort(grep { $_ > 0 } @_));
3 push @Np, $Np[-1] + 2;
4 (($Np[$_] + 1 < $Np[$_ + 1]) && return $Np[$_] + 1) for 0 .. $#Np - 1;
5 }
```

Line 2 filters out non-positive input numbers and *then* sorts them. I
also force the addition of a `0`

at the very beginning, it will not
alter the sorting of the whole thing *and* will allow me to simplify
looking through the array.

Line 3 adds another element that does not break the sorting *and* lets
me treat the *last* element as any other one (i.e. as an â€śinternalâ€ť
element).

Line 4 is a concession to some golfing, letâ€™s take a closer look to its
alternative *unrolled and readable* form:

```
4.1 for my $index (0 .. $#Np - 1) {
4.2 my $candidate = $Np[$index] + 1;
4.3 if ($candidate < $Np[$index + 1]) {
4.4 return $candidate;
4.5 }
4.6 }
```

We iterate over all but the last element, which was added by us. At each
loop, we compute what would be the *candidate* value, i.e. our possible
return value, which would be one more than the element we are currently
analyzing (line 4.2).

If this candidate is *less* than the next element in the array (line
4.3), then itâ€™s indeed missing and we can return it (line 4.4).

If you want to cut-and-paste, hereâ€™s a complete file for doing some experimentation:

```
#!/usr/bin/env perl
use 5.024;
use warnings;
use English qw< -no_match_vars >;
use experimental qw< postderef >;
no warnings qw< experimental::postderef >;
sub spnb {
my @Np = (0, sort(grep { $_ > 0 } @_));
push @Np, $Np[-1] + 2;
(($Np[$_] + 1 < $Np[$_ + 1]) && return $Np[$_] + 1) for 0 .. $#Np - 1;
}
for my $test (
[ 5, 2, -2, 0 ],
[ 1, 8, -1 ],
[2, 0, -1 ],
[],
[1, 2, 3],
) {
say spnb($test->@*);
}
```

Cheers!