The one about maximums

Weekly Challenge 218

Challenge, My solutions

Task 1: Maximum Product

Task

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.

My solution

This seemed straight forward. Sort the numbers numerically and multiple the three largest numbers to get a solution. But it's not that simple.

The last example shows that the solution is obtained by multiple the lowest two numbers and the largest number. We know that if we multiple an even number of negative integers, the result is positive. Multiplying an odd number of negative numbers is always a negative. Given that we only look at three digit, the maximum number of negative numbers is two, unless they are all negative.

So with this out of the way, I calculate the product of the three largest numbers, and the two lowest and largest number. I then display the maximum of these two values.

Examples

$ ./ch-1.py 3 1 2
6

$ ./ch-1.py 4 1 3 2
24

$ ./ch-1.py -1 0 1 3 1
3

$ ./ch-1.py -8 2 -9 0 -4 3
216

Task 2: Matrix Score

Task

You are given a m x n binary matrix i.e. having only 1 and 0.

You are allowed to make as many moves as you want to get the highest score.

A move can be either toggling each value in a row or column.

To get the score, convert the each row binary to dec and return the sum.

My solution

This challenge actually turned out easier than I thought it would be, thanks to the use of xor and a bit of logic. I start my setting the solution variable to 0, and xor_row to 1 less than 2 to the power of the number of columns. So if we have 4 columns, xor_row is 15 (or 1111 in binary notation).

The next thing I do is convert each row from a list (array in Perl) into a decimal number. In Python this is done with int(<binary>, 2), while in Perl this is done by calling oct("0b<binary>"), which seems counter-intuitive given octets are from 0-7. I digress.

The next part is which rows and columns to toggle. For the columns I have a loop from 0 to xor_row. I numerically xor that value with each number from the previous step. This ensures that we consider every combination of which columns we want to toggle.

Toggling the rows is much easier thankfully. We know that the maximum sum for each row is either when we have the integer from the above step, or the value xored with xor_row, so I calculate this for each row. If the sum of the rows is greater than the current solution, I update solution with the new value.

Examples

$ ./ch-2.py "[[0,0,1,1],[1,0,1,0],[1,1,0,0]]"
39

$ ./ch-2.py "[[0]]"
1