Power Hungry
Created: May 01, 2024
Last modified: Oct 11, 2026
TL, DR.
Power Hungry
============
Commander Lambda's space station is HUGE. And huge space stations take a LOT of power. Huge space stations with doomsday devices take even more power. To help meet the station's power needs, Commander Lambda has installed solar panels on the station's outer surface. But the station sits in the middle of a quasar quantum flux field, which wreaks havoc on the solar panels. You and your team of henchmen have been assigned to repair the solar panels, but you'd rather not take down all of the panels at once if you can help it, since they do help power the space station and all!
You need to figure out which sets of panels in any given array you can take offline to repair while still maintaining the maximum amount of power output per array, and to do THAT, you'll first need to figure out what the maximum output of each array actually is. 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). The final products may be very large, so give the solution as a string representation of the number.
Languages
=========
To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Python cases --
Input:
solution.solution([2, 0, 2, 2, 0])
Output:
8
Input:
solution.solution([-2, -3, 4, -5])
Output:
60
-- Java cases --
Input:
Solution.solution({2, 0, 2, 2, 0})
Output:
8
Input:
Solution.solution({-2, -3, 4, -5})
Output:
60Commander Lambda's station runs on solar panels, and a quantum flux field has them all messed up: some produce power, some produce nothing (0), and some actually drain it (negative values). We need to pick a group of panels, at least one, whose product is as large as possible, and return it as a string.
With 50 panels there are over a quadrillion possible subsets, so trying them all is out of the question. Good news: we don't have to. All it takes is thinking about what each kind of number does to a multiplication.
# Three kinds of panel, three rules
Positives: take them all. They're integers, so each one is at least 1, and multiplying by them never shrinks a positive product.
Zeros: leave them out. A single zero wipes everything to 0. They're only useful as a last resort, when there's no way to get anything positive.
Negatives: in pairs. This is the trick hinted at in the statement: a negative times a negative is a positive, so two negatives together act like one positive. The trouble starts when there's an odd number of them: one is left without a partner and has to sit out.
# Which negative sits out?
The one that contributes least, meaning the one closest to zero. Take [-2, -3, 4, -5], which has three negatives.
Leaving out -2 gives $(-3)(-5)(4) = 60$. Leaving out -5 instead would give
just $(-2)(-3)(4) = 24$. What matters is how big the number is, not its sign, and the big ones are
the ones we want to keep.
# The cases that trip you up
Those rules cover almost everything, but there are two corners where it's easy to slip:
A single panel. The subset can't be empty, so for [-4] the answer is -4, negative or not.
Apply "drop the unpaired negative" blindly and you're left with nothing.
Nothing positive to build. With something like [-4, 0, 0] there are no positives and the negative is alone.
The best we can do is pick a zero and answer 0.
# Pick your panels
Type some panels separated by commas, or roll a random set. The ones that make it into the product light up, the unpaired negative
gets crossed out, and the useless ones stay dashed. Try a single number, nothing but zeros and negatives, or fifty 1000s.
Maximum product: 30
# The code
My solution follows those rules to the letter:
It handles the single-panel case first and returns it as is (I picked up that edge case from this Code Review answer).
It walks through the panels: positives go straight into product, negatives go into a min-heap
(heapq), and zeros are simply skipped.
negative_even_size is the number of negatives rounded down to an even number. If there are no positives and
not a single pair of negatives, it returns "0".
Otherwise it pops that many negatives off the heap. Since it's a min-heap, the most negative ones come out first
(-5 before -3), so whatever's left over at the end is exactly the one closest to zero.
import heapq
def solution(xs):
# Your code here
if xs is None:
return "0"
# Edge case from: https://codereview.stackexchange.com/a/237472
if len(xs) == 1:
return str(xs[0])
product = 1
negative_numbers = list()
positive_numbers = 0
for i in xs:
if i > 0:
product *= i
positive_numbers += 1
if i < 0:
heapq.heappush(negative_numbers, i)
negative_even_size = len(negative_numbers) - len(negative_numbers) % 2
if positive_numbers == 0 and negative_even_size == 0:
return "0"
for _ in range(negative_even_size):
product *= heapq.heappop(negative_numbers)
return str(product)
Why return a string? Because the number can get enormous: fifty panels of 1000 give
$10^{150}$, a 151-digit number. Python doesn't care, since its integers grow as needed,
but in Java that won't fit in a long and you'd have to reach for BigInteger.
# Variant: no sorting at all
The heap sorts every negative, even though all we really need to know is which one is closest to zero. So here's another way:
multiply everything that isn't zero, keep track of the largest negative (highest_negative_number) along the way,
and if the count of negatives ends up odd, divide the product by that one. A single pass, no heap, no lists.
def solution(xs):
if xs is None:
return "0"
# Edge case from: https://codereview.stackexchange.com/a/237472
if len(xs) == 1:
return str(xs[0])
product = 1
positive_numbers, negative_numbers = 0, 0
highest_negative_number = float("-inf")
for i in xs:
if i==0: continue
product *= i
if i > 0:
positive_numbers += 1
if i < 0:
negative_numbers += 1
if i > highest_negative_number:
highest_negative_number = i
if positive_numbers == 0 and negative_numbers < 2:
return "0"
if negative_numbers % 2 == 1:
product //= highest_negative_number
return str(product)
Watch out for one case that's really easy to miss in this version: a lonely negative counts as "nothing positive" too.
With [-4, 0, 0] there's one negative, so checking for zero negatives isn't enough: the product would be -4,
dividing by -4 leaves 1, and the right answer is 0. That's why the condition is
negative_numbers < 2.
# Wrapping up
What looks like a combinatorics problem (which of all these subsets?) turns into a short list of rules once you look at what each kind of number does to a product. The hard part isn't the main idea, it's the corners: one panel, all zeros, a lonely negative. When an "obvious" solution fails, it's almost always on one of those.