Not a golfing solution, but one that doesn't assume an upper bound (although it will loop forever if there's no finite answer):
use strict;
use warnings;
use Test::More 'no_plan';
$| = 1;
my %cache;
sub exact {
my ($amount, @bills) = @_;
return $cache{$amount} if defined $cache{$amount};
return 1 if !$amount;
return 0 if $amount < 0;
foreach my $bill (@bills) {
return $cache{$amount} = 1 if exact($amount - $bill, @bills)
}
return $cache{$amount} = 0;
}
sub largest {
%cache = ();
my @bills = @_;
my $smallest = $bills [0];
return -1 if $smallest == 1;
my $start = 0;
my $prev = 0;
for (my $t = 1; 1; $t++) {
if (exact($t, @bills)) {
if ($prev) {
if ($t - $start + 1 == $smallest) {return $start - 1}
}
else {$start = $t}
$prev = 1;
}
else {
$prev = 0;
}
}
}
is (largest(6,9,20), 43);
is (largest(3,5), 7);
is (largest(6,11,20), 27);
is (largest(17,18,19,20), 101);
is (largest(2,3,5,10), 1);
is (largest(1000,1001,1002,1003,1004,1005), 199999);
__END__
ok 1
ok 2
ok 3
ok 4
ok 5
ok 6
1..6
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.