laurent_r

These are some answers to the Week 201 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

You are given an array of unique numbers.

Write a script to find out all missing numbers in the range 0..$n where $n is the array size.

Example 1

Input: @array = (0,1,3)
Output: 2

The array size i.e. total element count is 3, so the range is 0..3.
The missing number is 2 in the given array.

Example 2

Input: @array = (0,1)
Output: 2

The array size is 2, therefore the range is 0..2.
The missing number is 2.

Missing Numbers in Raku

The find-missing subroutine uses the (-),%20infix%20%E2%88%96) set difference operator to find all the elements in the prescribed range that do not belong to the input array. The (-) set-difference operator implicitly coerces its operands (arrays) into Sets, so that we don’t need to explicitly perform the conversion and end up with essentially a one-liner.

sub find-missing (@in) {
    return ~(|(0..@in.elems) (-) @in).keys.sort;
}
for (0, 1, 3), (0, 1), (0, 1, 3, 5, 7, 2) -> @test {
    say  (~@test).fmt("%-15s => "), find-missing @test;
}

This program displays the following output:

$ raku ./missing-numbers.raku
0 1 3           => (2)
0 1             => (2)
0 1 3 5 7 2     => (4 6)

Missing Numbers in Perl

Although Perl doesn’t have Raku sets and set operators, it is only mildly more complex to port the idea to Perl: we can store the input array into a hash and then use a grep to find the items of the prescribed range that do not belong to the input array.

use strict;
use warnings;
use feature "say";

sub find_missing {
    my %in = map {$_ => 1} @_;
    return grep { not exists $in{$_} } 0..scalar @_;
}
for my $test ([0, 1, 3], [0, 1], [0, 1, 3, 5, 7, 2]) {
    printf "%-15s => ", "@$test";
    say map "$_ ", find_missing @$test;
}

This program displays the following output:

$ perl ./missing-numbers.pl
0 1 3           => 2
0 1             => 2
0 1 3 5 7 2     => 4 6

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on February 5, 2023. And, please, also spread the word about the Perl Weekly Challenge if you can.