Foo Bar - Power Hungry challenge test case failing on unknown edge cases [closed]

Question

The challenge is to find the maximum product of a subset of a given array. Here's the problem:

Write a function solution(xs) that takes a list of integers representing the power output levels of each panel in an array, and returns the maximum product of some non-empty subset of those numbers. So for example, if an array contained panels with power output levels of [2, -3, 1, 0, -5], then the maximum product would be found by taking the subset: xs[0] = 2, xs[1] = -3, xs[4] = -5, giving the product 2*(-3)*(-5) = 30. So solution([2,-3,1,0,-5]) will be "30".

Each array of solar panels contains at least 1 and no more than 50 panels, and each panel will have a power output level whose absolute value is no greater than 1000 (some panels are malfunctioning so badly that they're draining energy, but you know a trick with the panels' wave stabilizer that lets you combine two negative-output panels to produce the positive output of the multiple of their power values).

My code basically removes all 0's inside the list, then I iterate over all the remaining integers in the array and put each one in their respective array (positive or negative numbers). I sort my array with negative numbers then check its length; if it's odd, then I remove the last element (which will always be the one closest to 0 since I sorted it). Finally, I multiply each number inside these two arrays and return the result (we need to return it as string).

def solution(xs):
    negatives = []
    positives = []
    product = 1

    xs = filter(lambda a: a != 0, xs)

    if not xs:
        return '0'

    for num in xs:
        if num > 0:
            positives.append(num)
        elif num < 0:
            negatives.append(num)

    if not positives and len(negatives) == 1:
        return '0'

    negatives.sort()

    if negatives:
        if len(negatives) % 2 != 0:
            negatives.pop()

    for x in positives + negatives:
        product *= x

    return str(product)

I've already search the internet as to why my logic is failing the fourth test case, I've read that if there's only one negative number in the array, you should return 0, but I also read that you should return the negative value. However, previously to writing the part of my code that checks this possibility, the fifth test case was also failing. So you need to return 0 in this case.

Here's the repl with my code, open test cases and some test cases that I've added.

Clearly there's an edge case that my code is failing but I can't figure out at all. Help, please?

Answer 1

You've got too much code.

First you filter out the zeros:

xs = filter(lambda a: a != 0, xs)

Then you filter the positives to one list and the negatives to another:

for num in xs:
    if num > 0:
        positives.append(num)
    elif num < 0:
        negatives.append(num)

So why bother with the first filtering? Zeros would go into neither list in this loop; they're naturally filtered out.

You sort the negatives array unnecessarily. You only need to do so if it contains an odd number of elements. And you don't need to protect the test of whether it contains an odd number of elements with a check if it contains any elements at all.

No positive values and 1 negative value seems an odd special case. If you let the code progress past that point, the single odd value would be pop'd out of the negative array, leaving no positive values and no negative values, which seems a less "special" special case.

Simplified code:

def solution(xs):
    negatives = [num for num in xs if num < 0]
    positives = [num for num in xs if num > 0]

    if len(negatives) % 2 != 0:
        negatives.sort()
        negatives.pop()

    if positives or negatives:
        product = 1
        for x in positives + negatives:
            product *= x

        return str(product)

    return '0'

This should behave the same as your original code (complete with not passing some edge cases), but should be slightly faster.

---

Do you really need to sort the negatives array? That is an \$O(N \log N)\$ operation. You just need to remove the smallest magnitude number from the array, and finding and removing that can be done in \$O(N)\$ time.

---

Edge Cases

What is the maximum product of a non-empty subset of [-4]?

I've read that if there's only one negative number in the array, you should return 0, but I also read that you should return the negative value.

Seems unreasonable to return zero in this case, because the only non empty subset is [-4], and the maximum product is -4.

But what about [-4, 0]? Both 0 > -4 and -4 * 0 > -4, so the maximum product is no longer -4.

Modification of the code left to student.