Codility MaxProductOfThree

Given a vector of integer, return the maximal value we could get multiplying any possible triplet.

You could find this problem, marked as painless, in the Sorting section, practicing area, on the codility web site.

And here is a test case, that I have translate for C++11 on GoogleTest, that is provided to make more clear the request:
TEST(MaxProductOfThree, Given)
{
    std::vector<int> input { -3, 1, 2, -2, 5, 6 };
    ASSERT_EQ(60, solution(input));
}
It is easy to spot that the maximal solution here is given by multiplying 2, 5, and 6, being them the biggest positive elements in the collection. Still, this test case it is not enough to capture all the interesting input data. It could happen also that we have two big negative elements, and we should remember that multiplying two negatives numbers gives a positive one.

I have already solved this problem some time ago, in a previous you could find my C++98 solution and some more testing and chatting about the requisites. Please have a look at it for more details.

Now Codility supports a C++11 compiler, and this is my refactoring for the new programming environment:
int solution(std::vector<int>& input)
{
    if(input.size() < 3) // 1
        return 0;

    std::sort(input.begin(), input.end()); // 2

    int pos = input.back() * *(input.rbegin() + 1) * *(input.rbegin() + 2); // 3
    int neg = input.front() * *(input.begin() + 1) * input.back(); // 4

    return std::max(pos, neg); // 5
}
1. Input checking is usually not considered for codility problems, still I didn't fill right not to state explicitly that we are expecting at least three elements in the input vector. Admittedly, throwing an exception would have been a more clean approach.
2. Checking all the triples would lead to a cubic time complexity. Much better to sort the collection, which costs a mere N*lgN.
3. Vanilla case, just pick the first three values to the left and multiply them.
4. Alternative solution, a couple of big negative values change the rule of the game. Get them, and multiply them to the one to the extreme left.
5. Compare the two tentative solutions, and return the big one.

If you think a bit about it, the pos and neg tentatives cover all the possible cases (all negative numbers, and any variation I could have thought of).

4 comments:

  1. very brilliant insight! It is more like a math problem than a coding problem.

    ReplyDelete
    Replies
    1. Thank you! Sometimes it is not clear where maths end and programming begins ;-)

      Delete
  2. You code will fail for input, {1,2,10,0,-1,-3,-6}
    which after sorting is, -6, -3, -1, 0 1 2 10, then

    you get in your code +18 or +20 in L, R end products. However the correct maximum is 30 = 10 x -3 x - 1!

    ReplyDelete
    Replies
    1. I beg to differ. My solution compares:

      (a) 1 x 2 x 10 = 20
      (b) -6 x -3 x 10 = 180

      And returns the second, that is bigger than your proposed solution.

      Is there anything I'm missing?

      Delete