Find the highest product between elements in a set [closed]

Question

I'm solving a programming challenge that essentially consists of finding the highest product of elements in a set.

This is my current solution, and is passing all the test cases but one. The test case that is failing is not available to me, so I kinda have to guess what is wrong with my code.

public static String solution(int[] xs) {
    if (xs.length == 1) {
        return Integer.toString(xs[0]);
    }

    Arrays.sort(xs);

    BigInteger productOfPositiveIntegers = BigInteger.ONE;
    BigInteger productOfNegativeIntegers = BigInteger.ONE;
    Vector<BigInteger> negativeIntegers = new Vector<>();
    BigInteger result;

    boolean areAllElementsZero = true;

    for (int element : xs) {
        if (element > 0) {
            productOfPositiveIntegers = productOfPositiveIntegers.multiply(new BigInteger(Integer.toString(element)));
            areAllElementsZero = false;
        } else if (element < 0) {
            negativeIntegers.add(new BigInteger(Integer.toString(element)));
            areAllElementsZero = false;
        }
    }

    if (areAllElementsZero) {
        return BigInteger.ZERO.toString();
    }

    if (negativeIntegers.size() % 2 == 0) {
        for (BigInteger element: negativeIntegers) {
            productOfNegativeIntegers = productOfNegativeIntegers.multiply(element);
        }
    } else {
        negativeIntegers.remove(negativeIntegers.size() - 1);
        for (BigInteger element: negativeIntegers) {
            productOfNegativeIntegers = productOfNegativeIntegers.multiply(element);
        }
    }

    if (productOfNegativeIntegers.compareTo(BigInteger.ZERO) == 1) {
        result = productOfPositiveIntegers.multiply(productOfNegativeIntegers);
    } else {
        result = productOfPositiveIntegers;
    }

    return result.toString();
}

My algorithm is essentially:

1. sort numbers from lowest to highest.
2. keep track negative numbers in a separate vector.
3. multiply all positive numbers
4. If the total number of negative numbers is even, multiply them all. If not, drop the lowest negative number and multiply all the negative ones.
5. If the product of all the negative numbers is bigger than zero, multiply the product of negative numbers with the product of all positive numbers.
6. Return solution.

These are the test cases that I'm passing to my method:

    int[] testCase = {2, 0, 2, 2, 0}; // should return "8"
    int[] testCase2 = {-2, -3, 4, -5}; // should return "60"
    int[] testCase3 = {2, -3, 1, 0, -5}; // should return "30"
    int[] testCase4 = {-4, -10, -2, -1, -5}; // should return "400"
    int[] testCase5 = {1, 2, 3, 4};
    int[] testCase6 = {0, 0, 0}; // should return "0"
    int[] testCase7 = {-1}; // should return "-1"
    int[] testCase8 = {-1, -1, -1}; // should return "1"

For example the first test case, should return 8 because the highest product would be:

2 * 2 * 2 = 8

Second test case is 60 because:

-4 * -5 * 4 = 60

Last test case is 1 because:

-1 * -1 = 1

My assumption is that my code is taking too long to run for the test case that is failing.

According to the challenge, the highest possible number is 1000, and the highest number of elements in the set would be 50, so the biggest product would be 1E150 When I pass that test case to my program, it runs in less than a second.

So my question is two parts really:

1. What can I do to speed this up? I'm casting integers to BigIntegers in a loop, so that hurts just to look at it. But I kinda need to do that anyways.

2. If performance is not the problem, and I'm missing one edge case, which one is it?

Also, if this is not a good question for this community please let me know and I'll be more than happy to remove the question.

Answer 1

Test case that could be failing: {0,-1}. In your case it returns 1 while it should have been 0.

About the algorithm:

• Since you are already sorting it, just multiply everything except zero and first negative number. If its still negative multiply the first negative number.

Answer 2

You can do a lot better. You don't need to sort (which takes O(n log n) time). You just need to multiply everything except zero keeping track of negative number closest to 0 and number of negative numbers insofar.

Example (in Python):

def solution(array):
    result = 1
    negcounter = 0
    greatest_negative = 0
    for e in array:
        if e < 0 and e > greatest_negative:
            e = greatest_negative
            negcounter += 1
            result *= e
        if not e == 0:
            result *= e
     if negcounter%2 == 1:
         result //= greatest_negative
     return result

It doesn't take into account cases where there is only one negative number, but it should be easy to deal with. This code runs in linear time with respect to the length of array, thus significant improvement.