| 27 June 2025 | Challenge 327 |
Absolutely Missing Differences
Task 1: Missing Integers
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @ints = (1, 2, 1, 3, 2, 5)
Output: (4, 6)
The given array has 6 elements.
So we are looking for integers in the range 1..6 in the given array.
The missing integers: (4, 6)
Example 2
Input: @ints = (1, 1, 1)
Output: (2, 3)
Example 3
Input: @ints = (2, 2, 1)
Output: (3)
Solution
Create a hash having the expected integers as keys, delete the given integers and sort the remaining keys.
use v5.24;
use warnings;
sub missing_ints {
(\my %ints)->@{1 .. @_} = ();
delete @ints{@_};
sort {$a <=> $b} keys %ints;
}
See the full solution to task 1.
Task 2: MAD
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: @ints = (4, 1, 2, 3)
Output: [1,2], [2,3], [3,4]
The minimum absolute difference is 1.
Pairs with MAD: [1,2], [2,3], [3,4]
Example 2
Input: @ints = (1, 3, 7, 11, 15)
Output: [1,3]
Example 3
Input: @ints = (1, 5, 3, 8)
Output: [1,3], [3,5]
Solution
Using the PDL shell to solve example 1 with rearranged elements to prevent values from coinciding with their index.
Create a matrix $diff holding all pair differences:
pdl> do_print 1
1
pdl> $i = long 4, 2, 3, 1
[4 2 3 1]
pdl> $diff = $i - $i(*1)
[
[ 0 -2 -1 -3]
[ 2 0 1 -1]
[ 1 -1 0 -2]
[ 3 1 2 0]
]
Create a matrix $l masking all unwanted pairs, i.e. elements paired with itself and reversed pairs.
This is a triangular matrix with 1’s in the lower left triangle:
pdl> $l = ones($diff)->tricpy(1)
[
[1 0 0 0]
[1 1 0 0]
[1 1 1 0]
[1 1 1 1]
]
Create the matrix $adiff as the absolute values of the differences, masking the unwanted pairs:
pdl> $adiff = abs($diff)->setbadif($l)
[
[BAD 2 1 3]
[BAD BAD 1 1]
[BAD BAD BAD 2]
[BAD BAD BAD BAD]
]
Find the indices $indx in $adiff where the minimum is taken:
pdl> $indx = whichND $adiff == $adiff->min
[
[2 0]
[2 1]
[3 1]
]
Look up the values corresponding to indices in $indx:
pdl> $pairs = $i->index($indx)
[
[3 4]
[3 2]
[1 2]
]
Order the numbers within the pairs:
pdl> $opairs = $pairs->qsort
[
[3 4]
[2 3]
[1 2]
]
Sort the ordered pairs lexicographically:
pdl> $opairs->qsortvec
[
[1 2]
[2 3]
[3 4]
]
Put everything together:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub mad_pairs {
my $i = long @_;
my $diff = $i - $i(*1);
my $adiff = abs($diff)->setbadif(ones($diff)->tricpy(1));
$i->index(scalar whichND $adiff == $adiff->min)->qsort->qsortvec;
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.