RabbitFarm
2025-06-29
Missing Integers Don’t Make Me MAD, Just Disappointed
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1: Missing Integers
You are given an array of n integers. Write a script to find all the missing integers in the range 1..n in the given array.
The core of the solution is contained in a single subroutine. The resulting code can be contained in a single file.
The approach we take is to use the given array as hash keys. Then we’ll iterate over the range 1..n and see which hash keys are missing.
-
sub find_missing{
my %h = ();
my @missing = ();
do{ $h{$_} = -1 } for @_;
@missing = grep {!exists($h{$_})} 1 .. @_;
return @missing;
}
◇
-
Fragment referenced in 1.
Just to make sure things work as expected we’ll define a few short tests.
-
MAIN:{
say q/(/ . join(q/, /, find_missing 1, 2, 1, 3, 2, 5) . q/)/;
say q/(/ . join(q/, /, find_missing 1, 1, 1) . q/)/;
say q/(/ . join(q/, /, find_missing 2, 2, 1) . q/)/;
}
◇
-
Fragment referenced in 1.
Sample Run
$ perl perl/ch-1.pl (4, 6) (2, 3) (3)
Part 2: MAD
You are given an array of distinct integers. Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.
We’ll use a hash based approach like we did in Part 1. The amount of code is small, just a single subroutine.
Since we need to have a nested loop to access all pairs we’ll make an effort to only do it once. What we’ll do is store the pairs in a list keyed by the differences. We’ll also track the minimum difference in a variable to avoid sorting to find it later.
-
sub mad_pairs{
my %mad = ();
my $mad = ~0;
for my $i (0 .. @_ - 1){
for my $j ($i + 1 .. @_ - 1){
my $d = abs($_[$i] - $_[$j]);
$mad = $d if $d < $mad;
push @{$mad{$d}}, [$_[$i], $_[$j]];
}
}
return @{$mad{$mad}};
}
◇
-
Fragment referenced in 4.
The main section is just some basic tests. Yeah, we’ll do lazy string formatting with chop!
-
MAIN:{
my $s = q//;
do{
$s .= q/[/ . join(q/, /, @{$_}) . q/], /;
} for mad_pairs 4, 1, 2, 3;
chop $s;
chop $s;
say $s;
$s = q//;
do{
$s .= q/[/ . join(q/, /, @{$_}) . q/], /;
} for mad_pairs 1, 3, 7, 11, 15;
chop $s;
chop $s;
say $s;
$s = q//;
do{
$s .= q/[/ . join(q/, /, @{$_}) . q/], /;
} for mad_pairs 1, 5, 3, 8;
chop $s;
chop $s;
say $s;
$s = q//;
}
◇
-
Fragment referenced in 4.
Sample Run
$ perl perl/ch-2.pl [4, 3], [1, 2], [2, 3] [1, 3] [1, 3], [5, 3]
References
posted at: 12:09 by: Adam Russell | path: /perl | permanent link to this entry