 # [Challenge] Max Product Finder

Basic Difficulty Python 3
https://repl.it/Imv8/0

solution for hard difficulty for MaxProductFinder(K) written in Python3.
I initial wrote a solution that deletes elements from the list.
I decided against it to as it will use unneccesary operations on redefining the list.
I realize that an iterater-based subfunction is better instead of reading in the entire list.
EDIT: When a list is input for a function, in fact a pointer to the list is given. Therefore the list is not copied.

Then again I realize that the sort-trick will not work… Cheers!

https://repl.it/ImpC/11

best regards from Switzerland.

1. Basic difficulty with Python3
``````def maxProductFinder(intArray):

intArrayP = [x for x in intArray if x > 0]
intArrayN = [x for x in intArray if x < 0]

intArrayP.sort()
intArrayP.reverse()
intArrayN.sort()

if len(intArrayN) >= 2:
return max([intArrayP * intArrayP * intArrayP, intArrayP * intArrayN * intArrayN])
else:
return intArrayP * intArrayP * intArrayP
``````
1. Intermediate difficulty
``````def maxProductFinderk(intArray, k):
intArrayP = [x for x in intArray if x > 0]
intArrayN = [x for x in intArray if x < 0]

intArrayP.sort()
intArrayP.reverse()
intArrayN.sort()

lenP = len(intArrayP)
lenN = len(intArrayN)

product = []
for x in range(max(0,(k-lenP)+(k-lenP)%2),min(k,lenN),2):
product1 = 1
for y in range(0,x):
product1 = product1 * intArrayN[y]

product2 = 1
for y in range(0,k-x):
product2 = product2 * intArrayP[y]

product.append(product1*product2)

return max(product)

``````

Rules and extra info:

Check out the whole category here, including things like why we even do code challenges:

1 Like

Basic, Intermediate Difficulty
Java…
Changed int to double for more flexibility

``````package nl.lucemans.challenge;

import java.util.ArrayList;
import java.util.HashMap;

public class Main {

/*
* main
*  - Highest Multiplication Finder
*  + args - Launch arguments of Java application
*/
public static void main(String[] args)
{
System.out.println("Calculating highest product...");

// Some random list that could exist of any number
Double[] list = new Double[]{5.0, 3.0, 7.0, 19.0};

// The work
ArrayList<Double> result = maxProductFinderK(list, 3, false);

// Just some nice console output
System.out.println("Highest product found of ");
for (Double d : result)
{
System.out.println(d);
}
}

/*
* maxProductFinder
*  - returns the highest number
*  + List - a list of all doubles
*  + allowSquares - if should allow number repetion
*/
public static ArrayList<Double> maxProductFinder(Double[] list, boolean allowSquares)
{
return maxProductFinderK(list, 2, allowSquares);
}

/*
* maxProductFinderK
*  - returns the highest number
*  + List - a list of all doubles
*  + k - the amount of multiplications to perform
*  + allowSquares - if should allow number repetion
*/
public static ArrayList<Double> maxProductFinderK(Double[] list, Integer k, boolean allowSquares)
{
HashMap<String, Double> format = formatList(list);

ArrayList<Double> result = new ArrayList<Double>();

for (int i = 0; i <= k; i++)
{
String highest = getHeighestNumber(format);
Double dhighest = format.get(highest);
if (!allowSquares)
format.remove(highest);
}

return result;
}

/*
* formatList
*  - returns the a list of all doubles linked to increasing strings
*  = Used to supported multiple of the same number
*  + List - a list of all doubles
*/
public static HashMap<String, Double> formatList(Double[] list)
{
HashMap<String, Double> result = new HashMap<>();
Integer last = 0;
for (Double d : list)
{
result.put(last.toString(), d);
last += 1;
}
return result;
}

/*
* getHeighestNumber
*  - returns the highest number
*  + List - a list of all doubles
*/
public static String getHeighestNumber(HashMap<String, Double> list)
{
Double h = null;
String hstr = null;
for (String str : list.keySet())
{
Double d = list.get(str);
if (h == null)
{
h = d;
hstr = str;
}
if (d > h)
{
h = d;
hstr = str;
}
}
return hstr;
}
}
``````

Intermediate\Hard difficulty

https://repl.it/InAO/1

Tried to keep the code as generic as possible without any blatant case partition.
Firstly, in case of an odd k, the product must contain the largest integer (note: not necessarily largest in terms of absolute value), so I made sure I always multiplied by it, and set it as 1 in case k is even.
The idea is that given a k, we will start by making two arrays, one with the k largest integers and one with the smallest k integers (or k-1 if k is odd which wont include the maximum of the array).
We then iterate on both arrays at the same time, multiplying the current two members of each array, including the larger product in the final product and moving the iterator forward two spots at the selected array. In order to include the case in which all integers are negative, I have also multiplied both sides by the “mustContain” value, which will flip the sign and pick the correct product. We finish the iteration once the sum of iterated members is k.
The final step is computing the product and returning it.

Time complexity: O(n+klogk), when using a heap to get a sorted array of the smallest and largest k integers.

1 Like

Basic Difficulty, java

``````import java.util.Arrays;

public class Main {

public static void main(String[] args) {

int[] array = {-6, -8, 4, 2, 5, 3, -1, 9, 10};

System.out.println(Main.maxProductFinder(array));
}

public static int maxProductFinder(int[] array){

Arrays.sort(array);

int number1, number2;

number1 = array * array * array[array.length-1];
number2 = array[array.length - 3] * array[array.length - 2] * array[array.length - 1];

if( number1 > number2 )
return number1;
else
return number2;

}
}
``````

https://repl.it/InOL/3

This is my first project, please be gentle with me…
Intermediate on Python 2

https://repl.it/InQP/0

Original code:
#I don’t know if this is the most elegant solution, but considering how new I am to coding, I think it’s pretty good.
def maxProductFinderK(sequence, K):
absolute =
#this will be a list of the absolute values of the items of sequence, with the largest negative number omitted, if there is an odd number of negative numbers in sequence
list2 = sorted(sequence)
#create a new list so as not to modify original
neg_count = 0
for a in list2:
if a != abs(a):
neg_count = neg_count + 1
#this counts how many negative numbers are in the original list
if neg_count % 2 != 0:
d = list2[neg_count-1]
list2.pop(neg_count - 1)
else:
d = 1
#this omits the largest negative if there is an odd number of negatives
for b in list2:
absolute.append(abs(b))
absolute = sorted(absolute)
#i now have a sorted list of the absolute values of the original list, minus the largest negative, in case of an odd number of negatives. This means that multiplying the last items in the list will give the maximum possible product, as long as the list is longer than K.
b = 1
for c in range(1, K+1):
if len(absolute) - c < 0:
b = bd
break
#this ensures that a list of length K which includes negatives will still yield the correct result. it also means the function can take arguments where K is larger than the length of the list without causing an error
else:
b = b
absolute[len(absolute)-c]

``````return b
``````

print maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 2)

Basic difficulty using C++ (with explanations)

https://repl.it/InRp/0

Basic, Intermediate, and Hard difficulties.

``````import java.util.Arrays;
public class Main
{
public static void main(String[] args)
{
int[] arr = {-6, -8, 4, 2, 5, 3, -1, 9, 10};
int k = 4;
System.out.println(maxProductFinder(arr));
System.out.println(maxProductFinderK(arr,k));
}
public static int maxProductFinder(int[] arr)
{
Arrays.sort(arr);
int leftProduct = arr*arr*arr[arr.length-1]; //take the two most negative values and the largest positive value
int rightProduct = arr[arr.length-3]*arr[arr.length-2]*arr[arr.length-1]; //take the three largest positive values
return (leftProduct > rightProduct) ? leftProduct : rightProduct; // pick the largest value
}
public static int maxProductFinderK(int[] arr, int k)
{
Arrays.sort(arr); // sorting takes O(nlgn)
int product = 1;
int i = 0, j = arr.length-1;
int leftProduct, rightProduct;
while(k > 3) // the base case is having 3 or 2 values left for our product
{
leftProduct = arr[i]*arr[i+1];
rightProduct = arr[j]*arr[j-1];
if(leftProduct > rightProduct || (arr[j-2] < 0 && k%2==1))
{
product *= leftProduct;
i += 2;
}
else
{
product *= rightProduct;
j -= 2;
}
k -= 2;
}
//base case
if(k == 3)
{
leftProduct = arr[i]*arr[i+1]*arr[j];
rightProduct = arr[j-2]*arr[j-1]*arr[j];
}
else
{
leftProduct = arr[i]*arr[i+1];
rightProduct = arr[j-1]*arr[j];
}
product *= ((leftProduct > rightProduct) ? leftProduct : rightProduct);
return product;
}
}
``````

https://repl.it/Im6q/23

My solution for maxProductFinder() starts by sorting the array, and then the largest product is either the multiplication of the three largest positive numbers `arr[arr.length-3]*arr[arr.length-2]*arr[arr.length-1]` or the product of the two smallest negative numbers times the largest positive number `arr*arr*arr[arr.length-1]`.
maxProductFinderK() first sorts the array, then iterates from both ends and picks each time the largest product among the two most negative values `leftProduct = arr[i]*arr[i+1];` and the two most positive values `rightProduct = arr[j]*arr[j-1];`, and the base case is when k = 3 (like the basic difficulty) or k = 2, which is just an extension of the while loop.
My code assumes that there are more items in the array than k and that there are enough positive values and pairs of negative values to obtain a positive product of k items.
It has O(nlgn + k) complexity because Arrays.sort() is O(nlgn) and the loop iterates at most (k-3)/2 times, but since k < n, the time complexity is O(n*lgn). (n is the number of items in the array).
Edit: My previous solution didn’t work incases where there are only negative values but an odd number of factors is needed. I modified it to take care of that by adding the condition `if(leftProduct > rightProduct || (arr[j-2] < 0 && k%2==1))`.

1 Like

Basic:
https://repl.it/InT9/1

Intermediate (and maybe hard) solution in Python 3.

The hard part of the challenge for me was dealing with the possibility of negative numbers. The key to my solution was realising positive or negative don’t matter, we just want the largest numbers. Then from there, we can test that there is an even amount of negative numbers (which will always give a positive result). If not, we replace the smallest negative with the next largest positive.

https://repl.it/In6J/0

``````def maxProductFinder(intList, k):

# We need to have an even number of negatives in the array
# so that we end up with a positive number
def evenNegs(prodList):
count = 0
for i in prodList:
if i < 0:
count += 1
if count % 2 == 0:
return True
else:
return False

# We want the largest list regarless of if they are negative or not
# the abs function will return based on distance from 0 which is what we want
strIntList = sorted(intList, key=abs, reverse = True)

# We can then grab k amount of numbers from the list knowing
# they will be the "largest" numbers
factorList = strIntList[0:k]

# Test if we have an even number of negative numbers
# If not, we want to replace the smallest negative...
if evenNegs(factorList) == False:
for x in range((len(factorList)) -1, -1, -1):
if factorList[x] < 0:
changeElement = x
break

# with the next highest positive number. This makes sure
# we always get a positive result
for y in range(k, len(strIntList), 1):
newElement = strIntList[y]
if newElement > 0:
newElement = strIntList[y]
break

factorList[changeElement] = newElement

product = 1
for x in factorList:
product *= x

return product

factors = [-8, 6, -7, 3, 2, 1, -9]
print(maxProductFinder(factors, 2))

``````

Basic Challenge/Python3:

https://repl.it/In6S/4

Anna

1 Like

Basic + Hard Solutions, Ruby

https://repl.it/In78/1

Fun challenge!

Beginning and intermediate challenges done in Python.
My experience with python is the Codecademy course. I first had to code my answer in my native language (IDL, which nobody knows) and then translate it to Python. It’s a great way to learn the language!

https://repl.it/In6X/8

Beginning solution is simple. The answer can either be the product of 3 positive numbers OR the product of 2 negative and 1 positive number. I sorted the list in ascending and descending order (not necessary, but it’s prettier). Using list slicing I grabbed the first 3 numbers from the descending list for the first answer. For the second answer I took the first two in the ascending list and the first number in the descending list. I didn’t want to multiply the 3 numbers using * because that’s just ugly. I originally imported numpy and used numpy.product (which was already hard for me to figure out, ha!), but then I read the instructions that said no imports. I looked up the Python built-in functions and found one called reduce, which collapses a list into a single value according to a lambda function. Although it’s not as pretty as product, reduce does the trick. (I suppose I could have used a for loop instead, but I wanted to try something new.) Last step is to simply return the maximum of the two products.

The intermediate solution wasn’t bad after I figured out the pattern for picking negative numbers, which is dependent on K. Solutions containing the largest product can have 0, 2, 4, …K negative numbers if K is even. If it’s odd then the maximum number of negative numbers is K-1. I defined a variable called ‘num_neg’ that contains the number of negative integers in a solution and used a while loop to calculate the product for each of these possibilities. I stored all of the products in a list. The maximum number in the list is the solution. Interestingly, my definition of “negative” doesn’t necessarily mean a negative number. It really means numbers at the beginning of my ascending list. If some of these are non-negative then the product might turn out to be negative. But that’s ok since the final solution is the maximum of the calculated products.

This solves the intermediate/hard difficulty with Javascript.

I noticed some posted solutions don’t address all use cases. This solution checks every combination with a recursive function - little brute-force-esk but gets the job done.

https://repl.it/InPZ/64

Here’s the full code:

``````// This script finds the maximum product in an array of numbers

numbers = [-8, 6, -7, 3, 2, 1, -9]
numberAmount = 2

let products = []
function maxProductFinderK(numberArr, k) {

// Create initial array of number indexes in the array to multiple
const multNumbers = []
for (let i=0 ; i<k ; i++) {
multNumbers.push(i)
}

// Recursively check every combo
return productRecursivator(multNumbers, 0, numberArr)
}

function productRecursivator(multNumbers, locationFromEnd, numberArr) {

// Push current product to products array
products.push(multNumbers.reduce((acc, val) => {
return acc *= numberArr[val]
}, 1))

let locationFromStart = multNumbers.length-locationFromEnd-1

// Check if found the end
if (multNumbers[locationFromStart] === numberArr.length-locationFromEnd-1) {

// If all locations are at the end, then everything has been checked
if (locationFromStart === 0) {
return products.reduce((acc, val) => Math.max(acc, val))

// If the previous location is at the end, go to the previous location
} else if (multNumbers[locationFromStart-1] === numberArr.length-(locationFromEnd+2)) {
return productRecursivator(multNumbers, locationFromEnd+1, numberArr)

// Set the previous location's index up 1 and all following locations to follow behind
} else {
multNumbers[locationFromStart-1]++

for (let i=locationFromStart ; i<multNumbers.length ; i++) {
multNumbers[i] = multNumbers[i-1] + 1
}

return productRecursivator(multNumbers, 0, numberArr)
}

// Current location not at end, so increment
} else {
multNumbers[locationFromStart] += 1

return productRecursivator(multNumbers, 0, numberArr)
}
}

maxProductFinderK(numbers, numberAmount)
``````