Peter
Peter Campbell Smith

Matching strings and missing numbers

Weekly challenge 208 — 13 March 2023

Week 208 - 13 Mar 2023

Task 2

Task — Duplicate and missing

You are given an array of integers in sequence with one missing and one duplicate.

Write a script to find the duplicate and missing integer in the given array. Return -1 if none found.

For the sake of this task, let us assume the array contains no more than one duplicate and missing.

Analysis

We need only compare each number $n with the one that follows it, $f. If $n == $f then that is the duplicate, and if $n + 2 == $f, then $n + 1 is the missing number.

There is, I suppose, an argument that a sequence like 2, 3, 4, 4, 5 meets the criteria of the challenge, in that 1 or 6 could be said to be missing because we are told there must be a missing number, but I have ignored that interpretation.

We are also told that (a) the list is sorted least to greatest, and that (b) there is exactly one duplicate and one missing number. My script checks that these are indeed the case and provides an error message if either (a) or (b) is false.

Try it 

Example: 1, 2, 3, 3, 5

Script


#!/usr/bin/perl # Peter Campbell Smith - 2023-03-13 use v5.28; use utf8; use warnings; # You are given an array of integers in sequence with one missing and one duplicate. # Write a script to find the duplicate and missing integer in the given array. # Return -1 if none found. You may assume the array contains no more than one duplicate # and missing. # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/208/2 dup_and_miss(1, 2, 3, 3, 5); dup_and_miss(7, 7, 8, 9, 11); dup_and_miss(7, 8, 9, 11, 11); dup_and_miss(4, 5, 6, 7, 8, 8, 9, 10, 11, 12, 13, 15); dup_and_miss(1, 2, 3, 4, 5); sub dup_and_miss { my (@list, $j, $duplicate, $missing); @list = @_; # scan through the list up to the second last entry for $j (0 .. scalar @list - 2) { # if this one is the same as the next one, then this one's a duplicate if ($list[$j] == $list[$j + 1]) { invalid(@list) if $duplicate; $duplicate = $list[$j]; # if this one is 2 less than the next one, then this one plus one is missing } elsif ($list[$j] + 2 == $list[$j + 1]) { invalid(@list) if $missing; $missing = $list[$j] + 1; # or the list is invalid } elsif ($list[$j] + 1 != $list[$j + 1]) { invalid(@list); } } say qq[\nInput: \@nums = (] . join(', ', @list) . q[)]; say qq[Output: ] . ((defined $duplicate and defined $missing) ? qq[Duplicate is $duplicate and Missing is $missing.] : -1); } sub invalid { say qq[\nInvalid input: \@list = (] . join(', ', @_) . q[)]; exit; }

Output


Input:  @nums = (1, 2, 3, 3, 5)
Output: Duplicate is 3 and Missing is 4.

Input:  @nums = (7, 7, 8, 9, 11)
Output: Duplicate is 7 and Missing is 10.

Input:  @nums = (7, 8, 9, 11, 11)
Output: Duplicate is 11 and Missing is 10.

Input:  @nums = (4, 5, 6, 7, 8, 8, 9, 10, 11, 12, 13, 15)
Output: Duplicate is 8 and Missing is 14.

Input:  @nums = (1, 2, 3, 4, 5)
Output: -1

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