Max product of three elements

[frek]

Hi all,

Task, in summary: Find the maximum product of three elements in an array of int type with at least 3 elements.
I'm sure this task is something you've already heard of but for me it's new, so I wrote this long but correct solution:

void sortElem(const std::vector<int>& A, std::vector<size_t>& indices) {

	size_t sz{ A.size() };
	int m1{ -1000 }, m2{ m1 }, m3{ m1 }, m4{ m1 }, m5{ m1 }, m6{ m1 };
	size_t i1{ 0 }, i2{ 0 }, i3{ 0 }, i4{ 0 }, i5{ 0 }, i6{ 0 };

	for (size_t i = 0; i < sz; ++i)
		if (abs(A[i]) > m1) {
			m1 = abs(A[i]);
			i1 = i;
		}
	for (size_t i = 0; i < sz; ++i)
		if (abs(A[i]) > m2 && i != i1) {
			m2 = abs(A[i]);
			i2 = i;
		}
	for (size_t i = 0; i < sz; ++i)
		if (abs(A[i]) > m3 && i != i1 && i != i2) {
			m3 = abs(A[i]);
			i3 = i;
		}
	for (size_t i = 0; i < sz; ++i)
		if (abs(A[i]) > m4 && i != i1 && i != i2 && i != i3) {
			m4 = abs(A[i]);
			i4 = i;
		}
	for (size_t i = 0; i < sz; ++i)
		if (abs(A[i]) > m5 && i != i1 && i != i2 && i != i3 && i != i4) {
			m5 = abs(A[i]);
			i5 = i;
		}
	for (size_t i = 0; i < sz; ++i)
		if (abs(A[i]) > m6 && i != i1 && i != i2 && i != i3 && i != i4 && i != i5) {
			m6 = abs(A[i]);
			i6 = i;
		}
	indices.push_back(i1);
	indices.push_back(i2);
	indices.push_back(i3);
	indices.push_back(i4);
	indices.push_back(i5);
	indices.push_back(i6);
}

void multiplySum(const int elem, const std::vector<int>& bigThreeElemVec, std::vector<int>& sumVec) {
	sumVec.push_back(elem * bigThreeElemVec[0] * bigThreeElemVec[1]);
	sumVec.push_back(elem * bigThreeElemVec[0] * bigThreeElemVec[2]);
	sumVec.push_back(elem * bigThreeElemVec[1] * bigThreeElemVec[2]);
}

int solution(std::vector<int>& A) {
	const size_t range{ 3 };
	if (A.size() == range)        // Only 3 elements
		return A[0] * A[1] * A[2];

	std::vector<size_t> indices;

	if (A.size() > range * 2) {
		sortElem(A, indices);

		bool neg{ true };
		for (size_t i = 0; i < range * 2; ++i)
			if (A[indices[i]] >= 0)
				neg = false;

		if (neg) {  // all 6 elements are negative
			auto it{ std::max_element(A.begin(), A.end()) };
			if (*it >= 0)
				A[indices[indices.size() - 1]] = *it;
		}
	}
	else
		for (size_t i = 0; i < A.size(); ++i)
			indices.push_back(i);

	std::vector<int> firstBigThreeElem, secondBigThreeElem;
	for (size_t i = 0; i < indices.size(); i++)
		if (i <= 2)
			firstBigThreeElem.push_back(A[indices[i]]);
		else 
			secondBigThreeElem.push_back(A[indices[i]]);
	
	std::vector<int> sumVec;
	sumVec.push_back(firstBigThreeElem[0] * firstBigThreeElem[1] * firstBigThreeElem[2]);

	if(secondBigThreeElem.size() == range)
		sumVec.push_back(secondBigThreeElem[0] * secondBigThreeElem[1] * secondBigThreeElem[2]);

	for (size_t i = 0; i < secondBigThreeElem.size(); ++i)
		multiplySum(secondBigThreeElem[i], firstBigThreeElem, sumVec);

	if(secondBigThreeElem.size() == range)
		for (size_t i = 0; i < range; ++i)
			multiplySum(firstBigThreeElem[i], secondBigThreeElem, sumVec);
	else if(secondBigThreeElem.size() == range -1)
		for (size_t i = 0; i < range; ++i) 
			sumVec.push_back(firstBigThreeElem[i] * secondBigThreeElem[0] * secondBigThreeElem[1]);

	return *max_element(sumVec.begin(), sumVec.end()); 
} 

1) Is it not an O(n) solution, please? Why?

Then when I found (on the Web) that there's rule in this case saying: max product of three elements in the array is either the multiplication of the three greatest elements or the two lowest * the greatest, I wrote this simpler one:

int solution(std::vector<int>& A) {

	if (A.size() == 3)        // Only 3 elements
		return A[0] * A[1] * A[2];

	std::vector<int> maxThree;

	for (size_t i = 0; i < 3; ++i) {
		auto it{ std::max_element(A.begin(), A.end()) };
		maxThree.push_back(*it);
		A.erase(it);
	}

	std::vector<int> minTwo;

	for (size_t i = 0; i < 2; ++i) {
		auto it{ std::min_element(A.begin(), A.end()) };
		if (it != A.end()) {
			minTwo.push_back(*it);
			A.erase(it);
		}
	}

	std::vector<int> sum;
	sum.push_back(maxThree[0] * maxThree[1] * maxThree[2]);

	for (size_t i = 0; i < minTwo.size(); i++) {
		sum.push_back(minTwo[i] * maxThree[0] * maxThree[1]);
		sum.push_back(minTwo[i] * maxThree[0] * maxThree[2]);
		sum.push_back(minTwo[i] * maxThree[1] * maxThree[2]);
	}

	if (minTwo.size() == 2)
		for (size_t i = 0; i < maxThree.size(); i++) {
			sum.push_back(maxThree[i] * minTwo[0] * minTwo[1]);
			sum.push_back(maxThree[i] * minTwo[0] * minTwo[1]);
			sum.push_back(maxThree[i] * minTwo[0] * minTwo[1]);
		}

	return *std::max_element(sum.begin(), sum.end());
}

2) My second question is, from where should I have known about that rule? :(
I dedicated much time for the first solution, but when done and searching on the Web I found the rule!
How can I find the source of those rules that are useful for programming algorithms, please?

[dhayden]

It looks like O(n) to me.

As for the rule, it's mathematical intuition. If the numbers are all positive integers then the largest product is the product of the 3 largest numbers. You can prove that by contradiction:
- suppose the largest product is NOT the three largest numbers.
- Take the smallest number and replace it with one of the three largest that isn't already in the solution.
- The answer of this new product is larger than the previous one because you're multiplying the two original numbers by a larger third number.

If they can be positive and negative then it might be the two smallest times the largest if the two smallest are both negative. For example, in the set -10, -9, 1, 2, 3, the largest product is -10 * -9 + 3 = 270.

[frek]

Codility marks both solutions above O(n log n) while to me they're both O(n).

I can see that those solutions are of mathematics but where can I find a source of such mathematical rules useful for programming algorithms, please?

[lastchance]

Like @dhayden, I think that your first solution is O(N) - but it will have a large constant in front of that N. You could always try generating some large vectors for trial and timing a number of repeats.

Your solution isn't a "rule" - it's a particular observation that fits this particular problem.

The best way of finding them is probably doing it by hand with pen and paper and seeing what happens.

[frek]

The best way of finding them is probably doing it by hand with pen and paper and seeing what happens.

I dedicated much time working on finding some so-called "particular observation" using pen and paper by hand but the first correct and O(n) solution was the one I posted first. Then I told myself, let's have a look on the Web. Then occasionally found that there's a way if known the time for solving the task will be much shorter. I was quite sad why I couldn't find that in the first place. But it was not my fault since it's the first time I hear that the mac product of three can be calculated that simple way.
That's why I assume there must be some math source I can study and learn new techniques to create better algorithms in short time.

[lastchance]

But it was not my fault since it's the first time I hear that the mac product of three can be calculated that simple way.
That's why I assume there must be some math source I can study and learn new techniques to create better algorithms in short time.

No, somebody else has sat down and puzzled it out.

I imagine that they considered the possible number of negative numbers involved ...

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int solution( vector<int> &A )
{
   partial_sort( A.begin(), A.begin() + 2, A.end() );
   int low = A[0] * A[1];
   partial_sort( A.begin(), A.begin() + 3, A.end(), greater<int>() );
   return max( low * A[0], A[0] * A[1] * A[2] );
}

int main()
{
   vector<int> A = { -10, -4, 11, -3, 7, 3, 8, -12 };
   cout << solution( A ) << '\n';
}

[frek]

Yes, that's the simplest algo. (Of course I wasn't aware of partial_sort already! :) )
Again, do you believe that the right method to discover a good way to create a great algorithm for a given task is just by working on it (using pen and paper, for example) and trying to find a relationship in it?

[lastchance]

do you believe that the right method to discover a good way to create a great algorithm for a given task is just by working on it (using pen and paper, for example) and trying to find a relationship in it?

If you had seen something similar in the past you would, for efficiency, use that. So, experience counts.

However, there are quite of lot of problems where I, at least, just choose a few sets of numbers and work out the result by hand. You can then often spot a pattern and then you can try to prove it. (Dealing with the "edge cases" can sometimes be a pain.)

Actually, with your problem, I was originally going to come back and ask you if all the input numbers were positive (in which case the solution is obvious). Then I realised that the only significant issue was if negative numbers were involved (since multiplying two large negative numbers would produce a large positive). Your "rule" is really only finding a way of circumventing that issue - and there are other ways of doing it.

[seeplus]

That's why I assume there must be some math source I can study and learn new techniques to create better algorithms in short time.

There are several books on algorithms available. A quick search on Amazon reveals many. Some are intro, some are advanced. If you're into algorithms then I'd suggest you investigate some of these. Once you have knowledge and experience of algorithms then when you come up against an algorithm type problem that you haven't met before then you can call upon your knowledge and experience to come up with an algorithm. Note that in this case the algorithm is the important aspect - not the language. Once you understand an algorithm that it should be fairly easy to implement in the required language.