blob: b88384b28d5f065e6d49b92d3552abf0eda7ded9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
use warnings;
use strict;
use v5.38;
sub make_change_v1( $amount ) {
my @dynamic_arr = (1) x ( $amount + 1 );
my @coins = (5, 10, 25, 50);
for my $coin_amount (@coins) {
for my $idx ($coin_amount..$amount) {
$dynamic_arr[ $idx ] += $dynamic_arr[ $idx - $coin_amount ];
}
}
return $dynamic_arr[ -1 ];
}
sub make_change_v2( $amount ) {
# uses the fact that all coins not pennies are divisible by 5 to be 5 x more efficient
$amount = int( $amount / 5 );
return 1 if $amount == 0;
my @dynamic_arr = (1) x ( $amount + 1 );
my @coins = (1, 2, 5, 10);
for my $coin_amount (@coins) {
for my $idx ($coin_amount..$amount) {
$dynamic_arr[ $idx ] += $dynamic_arr[ $idx - $coin_amount ];
}
}
return $dynamic_arr[ -1 ];
}
my @inputs = (
9, 15, 100
);
for my $input (@inputs) {
say $input . ' => ' . make_change_v1( $input );
}
for my $input (@inputs) {
say $input . ' => ' . make_change_v2( $input );
}
|
