Peter
Peter Campbell Smith

Missing numbers and
piles of pennies

Weekly challenge 201 — 23 January 2023

Week 201: 23 Jan 2023

Task 1

Task — Missing numbers

We are given an array of unique numbers and asked to write a script to find out all missing numbers in the range 0..$n where $n is the array size.

Analysis

The first thing to note is that there will always be at least one missing number, as there are $n + 1 numbers in the range 0 .. $n and only $n entries in the array.

The easy way to do this task is to convert the array to a string:

$string = ',' . join(',', @$array) . ',';

The string will look something like this:

,1,2,3,4,5,6,

Now all we have to do is to loop $j over 0 to $n - 1 and:

$result .= qq[$j, ] unless $string =~ m|,$j,|;

and with a little tidying up of the format, we have the result requested.

Try it 

Example: 1, 2, 4, 5, 6

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2023-01-23
# PWC 201 task 1

use v5.28;
use utf8;
use warnings;

# Task: 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.

# Blog: https://pjcs-pwc.blogspot.com/2023/01/201-missing-numbers-and-piles-of-pennies.html

my (@tests, $test, $string, $j, $result);

@tests = ([0, 1, 3], [0, 1], [4, 5, 6], [6, 5, 4, 2, 1, 0], [0], []);

# loop over tests
for $test (@tests) {
    
    # make a string from the array
    $result = '';
    $string = ',' . join(',', @$test) . ',';   # $string = ,1,2,3,
    
    # check for missing numbers
    for $j (0 .. scalar @$test) {
        $result .= qq[$j, ] unless $string =~ m|,$j,|;
    }
    
    # report result
    $string =~ s|,|, |g;
    say qq[\nInput:  \$array = (] . substr($string, 2, -2) . ')';
    say qq[Output: ] . substr($result, 0, -2);
}   

Output


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

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

Input:  $array = (4, 5, 6)
Output: 0, 1, 2, 3

Input:  $array = (6, 5, 4, 2, 1, 0)
Output: 3

Input:  $array = (0)
Output: 1

Input:  $array = ()
Output: 0

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain