1
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by ferada, mdfst13, Tunaki, Vogel612, Mast Nov 4 '16 at 13:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – ferada, mdfst13, Tunaki, Vogel612, Mast
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ I think the approach should be: retain all strictly positive numbers and multiply them. Then retain every 2 consecutive negative numbers (sorted descendingly in absolute value) and multiply that also. If there was nothing to consider, there should be either a single value left, and that's the answer, or the array was empty (and what should be returned there? maybe that's your issue). \$\endgroup\$ – Tunaki Nov 3 '16 at 20:27
  • \$\begingroup\$ I thought about empty array, but I do not know what to do with an empty array. The problem doesn't specify. Nevermind the problem specifies that a non-empty array will be passed. \$\endgroup\$ – ILikeTacos Nov 3 '16 at 20:32
  • \$\begingroup\$ just wondering: you use negativeIntegers.add(new BigInteger(Integer.toString(element))); , why not negativeIntegers.add(BigInteger.valueOf(element));? \$\endgroup\$ – Timothy Truckle Nov 3 '16 at 20:39
  • \$\begingroup\$ @TimothyTruckle that's a good call -- I just updated it \$\endgroup\$ – ILikeTacos Nov 3 '16 at 20:42
  • \$\begingroup\$ What should be returned on things like { 2, -2 }? Would be 2 without multiplication, or -4? Could you link to the challenge if possible? \$\endgroup\$ – Tunaki Nov 3 '16 at 20:46
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

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