0
$\begingroup$

🧩 How do you find the highest product of X items?

This should optimize for runtime complexity and protect from overflows from large products.

  • Inputs
    1. An array of both positive and negative Ints representing potential products to the solution
    2. An Int representing the number of products required for the solution
  • Output: An Int representing the highest product of X amount of numbers.

For example, for the highest product of 3 items, the input is iterated through while updating the following variables. After the iteration has completed in $O(n)$ time, the highest product of three variable is returned as the solution.

  • Lowest number
  • Highest number
  • Lowest product of two
  • Highest product of two
  • Highest product of three
$\endgroup$
2
  • 2
    $\begingroup$ Are the input numbers positive? Why isn't this just the product of the $X$ largest input numbers? $\endgroup$ – Steven Dec 3 '20 at 17:12
  • $\begingroup$ Steven, thanks for the comment. I've updated the post to indicate that the input can be both positive and negative numbers. $\endgroup$ – Adam Hurwitz Dec 4 '20 at 14:17
1
$\begingroup$

Let the integers be $a_1,a_2,\dots,a_n$ sorted in decreasing order of magnitude, so $|a_1| \ge |a_2| \ge \cdots$, and suppose you want to find the product of $k$ of them that is as large as possible.

Then:

  • If $a_1 \times \cdots \times a_k$ is positive, it is the solution.

  • Otherwise, if $a_{k+1}$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit $a_i$ from the product, where $a_i$ is the largest of the negative numbers in $a_1,\dots,a_k$, i.e., closest to zero).

  • Otherwise, if $a_{k+1}$ is negative and at least one of $a_1,\dots,a_k$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit the smallest positive number of $a_1,\dots,a_k$ from the product).

  • Otherwise, if at least one of $a_1,\dots,a_n$ is positive, the solution is $a_1 \times \cdots \times a_{k-1} \times a_j$ where $a_j$ is the largest positive number in $a_1,\dots,a_n$.

  • If all of $a_1,\dots,a_n$ are negative and $k$ is odd, then the solution is $a_{n-k+1} \times \dots \times a_n$.

This can be computed in $O(n \lg k)$ time using a heap of size $k$.

$\endgroup$
1
  • $\begingroup$ @Dmitry, good point! I've revised my answer. I hope I've covered all the cases now. $\endgroup$ – D.W. Dec 5 '20 at 21:06
0
$\begingroup$

Time Complexity: $O(nlogn)$

Space Complexity: $O(n)$

  1. Sort the $input$ array.

  2. If the last item is positive, find the product for the first $n$ items.

  3. If the last item is negative, count how many $negativeItems$ exist up to $n$, and then round the number, $negativeItems$, down to the closest even number.

  4. Starting with the smallest negative item, compare it to the largest item at the beginning of the $input$ array. Then compare the next largest negative item with the second-largest item, and so forth until all $negativeItems$ are compared.

    4a. Add the original value of the result of whichever number contains the greater absolute value into the $productArray$.

    4b. Add the remaining positive items, $n - negativeItems$, to the $productArray$.

  5. Calculate the product from the $productArray$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.