extra number

extra.pl

use strict;
use warnings;

use Data::Dumper;
use List::Util qw(shuffle);

my $max   = int rand(18) + 2;
my @array = shuffle 1 .. $max;
push @array, $array[int rand $max];

my $sum = int($max * $max / 2) + ($max + $max % 2) / 2;
# my $sum = $max * ($max - $max % 2) / 2 + ($max % 2 ? $max : $max / 2);

print "sum 1 .. $max = $sum \n";

$sum -= $_ for @array;

print "extra number is ", abs $sum, "\n";
print '=' x 20, "\n";
print Dumper(\@array);

__END__
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given an array of length n + 1 whose elements belong to the set {1, 2, ..., n}.
By the pigeonhole principle, there must be a duplicate. Find it in linear time and space.