Peter Campbell Smith

Multiply three
and binary matrix

Weekly challenge 218 — 22 May 2023

Week 218 - 22 May 2023

You are given a list of 3 or more integers. Write a script to find the 3 integers whose product is the maximum and return it.

Analysis

We are asked for 'the maximum' and I am going to assume that's the nearest to plus infinity. So given -3 and 2 then 2 is the maximum.

With that settled, here is the algorithm:

• Reverse sort the list by absolute value using
sort { abs(\$b) <=> abs(\$a) }.
• Take the first three numbers in the list and multiply then together to give \$product
• If \$product is positive, or if the list has only 3 numbers - that's the answer.
• If \$product is negative, subtract from \$product the last negative item of the three, and multiply \$product by the next positive item (or zero) in the list - and that's the answer.

Here's a couple of examples. The sorted list is 7, -6, 5, -4, 3, 2, 1

We multiply 7 x -6 x 5 = -210. That's negative, so we remove -6 which is the last negative number in our triplet. We can't use -4 because it's negative, but we can use 3, so now we have 7 x 5 x 3 = 105.

We multiply -7 x -6 x 5 = 210. That's positive, so that's the answer.

However, if all the numbers in the list are negative the above won't work, for example if the list is -7, -6, -5, -4, -3. Clearly no three numbers from that list will multiply to a positive number, so in this case the maximum product - see my assumption above - is the product of the last 3 numbers in the sorted list, in this case -5 x -4 x -3 = -60

You might ask 'what if one or more of the numbers are zero?' A few experiments show that the algorithm still works, for example: 3, 2, 0 yields zero, 4, 3, 2, 0 yields 24 and -3, -2, -1, 0 yields -3 x -2 x 0 = 0, which is correct as no other product of three of that list yields a positive result.

Try it

Example: 1, 2, 3, 4, 5

Script

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-05-22
use utf8;     # Week 218 task 1 - Maximum product
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

max_product(1, 2, 3, 4, 5);
max_product(-8, 2, -9, 0, -4, 3);
max_product(-9, -8, -7, -6, -5);
max_product(5, 6, 0);

sub max_product {

my (@list, \$product, \$count, \$j, \$last_negative, \$explain, \$k, \$last, \$negatives);

@list = @_;
say qq[\nInput:  (] . join(', ', @list) . ')';
@list = sort { abs(\$b) <=> abs(\$a) } @list;

\$product = 1;
\$count = 3;
\$last = scalar @list - 1;
die 'Not enough data' if \$last < 2;

# check for special case where list is all negatives
\$negatives = 0;
\$negatives += \$_ < 0 ? 1 : 0 for @list;

# not the special case
if (\$negatives != \$last + 1) {
for \$k (0 .. \$last) {

# multiply next number into product
\$j = \$list[\$k];
\$product *= \$j;
\$explain .= qq[\$j x ];

# note last negative one in case we need to back it out
\$last_negative = \$j if \$j < 0;
\$count --;

# if we've multiplied 3 and the result is +ve then we're done
if (\$count == 0) {
last if \$product >= 0;

# and we're done if there are no more entries
last if \$k == \$last;

# else we need to back out the last negative one and try again
\$product /= \$last_negative;
\$explain =~ s|\$last_negative x ||;
\$count = 1;
}
}

# special case
} else {
\$product = \$list[\$last - 2] * \$list[\$last - 1] * \$list[\$last];
\$explain =  qq[\$list[\$last - 2] x \$list[\$last - 1] x \$list[\$last] x ];

}
say qq[Output: \$product = ] . substr(\$explain, 0, -3);
}

Output

Input:  (1, 2, 3, 4, 5)
Output: 60 = 5 x 4 x 3

Input:  (-8, 2, -9, 0, -4, 3)
Output: 216 = -9 x -8 x 3

Input:  (-9, -8, -7, -6, -5)
Output: -210 = -7 x -6 x -5

Input:  (5, 6, 0)
Output: 0 = 6 x 5 x 0