Multiply three

and binary matrix

Weekly challenge 218 — 22 May 2023

Week 218 - 22 May 2023

Task 1

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.

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.

Now let's start with `-7, -6, 5, -4, -3, 2, -1)`

.

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.

#!/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); }

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain