Problem
Find the maxProduct of three numbers from a given integer array.
1. Handle all the cases
2. Interviewer was looking for a complete code
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the maxProduct of three numbers from a given integer array.
Created Date : 12-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
void PrintInfo(int a, int b, int c)
{
cout << "Max product of three is ";
cout << a << " * ";
cout << b << " * ";
cout << c << " * ";
cout << " = " << a * b * c << endl;
}
int FindMaxProductOfThree(int* arr, int s)
{
sort(arr, arr + s);
cout << "after sorting :" << endl;
copy(arr, arr + s, ostream_iterator<int>(cout, " "));
cout << endl;
if(arr[s - 1] <= 0 || arr[0] >= 0){
PrintInfo(arr[s - 1], arr[s - 2], arr[s - 3]);
return arr[s - 1] * arr[s - 2] * arr[s - 3];
}
int* arr1 = new int[s];
copy(arr, arr + s, arr1);
sort(arr1, arr1 + s, [=](int i, int j) ->bool {return abs(i) < abs(j);});
cout << "after sorting by abs " << endl;
copy(arr1, arr1 + s, ostream_iterator<int>(cout, " "));
cout << endl;
int neg[2];
int pos[3];
int negCount = 0;
int posCount = 0;
for(int i = s - 1; i >=0; --i){
if(arr1[i] > 0 && posCount < 3){
pos[posCount++] = arr1[i];
}
if(arr1[i] <= 0 && negCount < 2){
neg[negCount++] = arr1[i];
}
if(posCount == 3 && negCount == 2){
break;
}
}
delete[] arr1;
if(posCount < 3){
PrintInfo(pos[0], neg[0], neg[1]);
return pos[0] * neg[0] * neg[1];
}
if(negCount < 2){
PrintInfo(pos[0], pos[1], pos[2]);
return pos[0] * pos[1] * pos[2];
}
if(neg[0] * neg[1] > pos[1] * pos[2]){
PrintInfo(pos[0], neg[0], neg[1]);
return pos[0] * neg[0] * neg[1];
}
else{
PrintInfo(pos[0], pos[1], pos[2]);
return pos[0] * pos[1] * pos[2];
}
return 0;
}
int main(int argc, char* argv[])
{
cout << "Testing non-negtive array " << endl;
for(int s = 5; s < 15; ++s){
int* arr = new int[s];
for(int i = 0; i < s; ++ i){
arr[i] = rand() % 10;
cout << setw(4) << arr[i];
}
cout << endl;
int product = FindMaxProductOfThree(arr, s);
delete[] arr;
cout << endl;
}
cout << "-------------------------------" << endl;
cout << "Testing non-positive array " << endl;
for(int s = 5; s < 15; ++s){
int* arr = new int[s];
for(int i = 0; i < s; ++ i){
arr[i] = - rand() % 10;
cout << setw(4) << arr[i];
}
cout << endl;
int product = FindMaxProductOfThree(arr, s);
delete[] arr;
cout << endl;
}
cout << "-------------------------------" << endl;
cout << "Tesing mixed array " << endl;
for(int s = 5; s < 15; ++s){
int* arr = new int[s];
for(int i = 0; i < s; ++ i){
arr[i] = rand() % 10 - 5;
cout << setw(4) << arr[i];
}
cout << endl;
int product = FindMaxProductOfThree(arr, s);
delete[] arr;
cout << endl;
}
return 0;
}
Output
Testing non-negtive array
1 7 4 0 9
after sorting :
0 1 4 7 9
Max product of three is 9 * 7 * 4 * = 252
4 8 8 2 4 5
after sorting :
2 4 4 5 8 8
Max product of three is 8 * 8 * 5 * = 320
5 1 7 1 1 5 2
after sorting :
1 1 1 2 5 5 7
Max product of three is 7 * 5 * 5 * = 175
7 6 1 4 2 3 2 2
after sorting :
1 2 2 2 3 4 6 7
Max product of three is 7 * 6 * 4 * = 168
1 6 8 5 7 6 1 8 9
after sorting :
1 1 5 6 6 7 8 8 9
Max product of three is 9 * 8 * 8 * = 576
2 7 9 5 4 3 1 2 3 3
after sorting :
1 2 2 3 3 3 4 5 7 9
Max product of three is 9 * 7 * 5 * = 315
4 1 1 3 8 7 4 2 7 7 9
after sorting :
1 1 2 3 4 4 7 7 7 8 9
Max product of three is 9 * 8 * 7 * = 504
3 1 9 8 6 5 0 2 8 6 0 2
after sorting :
0 0 1 2 2 3 5 6 6 8 8 9
Max product of three is 9 * 8 * 8 * = 576
4 8 6 5 0 9 0 0 6 1 3 8 9
after sorting :
0 0 0 1 3 4 5 6 6 8 8 9 9
Max product of three is 9 * 9 * 8 * = 648
3 4 4 6 0 6 6 1 8 4 9 6 3 7
after sorting :
0 1 3 3 4 4 4 6 6 6 6 7 8 9
Max product of three is 9 * 8 * 7 * = 504
-------------------------------
Testing non-positive array
-8 -8 -2 -9 -1
after sorting :
-9 -8 -8 -2 -1
Max product of three is -1 * -2 * -8 * = -16
-3 -5 -9 -8 -4 0
after sorting :
-9 -8 -5 -4 -3 0
Max product of three is 0 * -3 * -4 * = 0
-7 -6 -3 -6 -1 -5 -4
after sorting :
-7 -6 -6 -5 -4 -3 -1
Max product of three is -1 * -3 * -4 * = -12
-2 0 -9 -7 -3 -7 -2 -6
after sorting :
-9 -7 -7 -6 -3 -2 -2 0
Max product of three is 0 * -2 * -2 * = 0
0 -1 -6 -5 -7 -5 -4 -1 -2
after sorting :
-7 -6 -5 -5 -4 -2 -1 -1 0
Max product of three is 0 * -1 * -1 * = 0
0 0 -1 -4 -6 0 -7 -1 -7 -7
after sorting :
-7 -7 -7 -6 -4 -1 -1 0 0 0
Max product of three is 0 * 0 * 0 * = 0
-7 -7 -3 -3 -5 -9 -9 -8 -1 -8 -2
after sorting :
-9 -9 -8 -8 -7 -7 -5 -3 -3 -2 -1
Max product of three is -1 * -2 * -3 * = -6
-6 -6 0 -3 -8 0 -1 -2 -5 0 -9 -4
after sorting :
-9 -8 -6 -6 -5 -4 -3 -2 -1 0 0 0
Max product of three is 0 * 0 * 0 * = 0
-7 -8 -3 -5 -1 -2 0 -1 -6 -4 0 -6 -1
after sorting :
-8 -7 -6 -6 -5 -4 -3 -2 -1 -1 -1 0 0
Max product of three is 0 * 0 * -1 * = 0
-8 -9 -8 -4 -1 -4 -3 -9 -8 -8 0 -8 -7 -7
after sorting :
-9 -9 -8 -8 -8 -8 -8 -7 -7 -4 -4 -3 -1 0
Max product of three is 0 * -1 * -3 * = 0
-------------------------------
Tesing mixed array
3 -2 3 -2 2
after sorting :
-2 -2 2 3 3
after sorting by abs
-2 -2 2 3 3
Max product of three is 3 * 3 * 2 * = 18
-4 -5 2 -2 -1 4
after sorting :
-5 -4 -2 -1 2 4
after sorting by abs
-1 -2 2 -4 4 -5
Max product of three is 4 * -5 * -4 * = 80
1 0 -4 -5 4 4 1
after sorting :
-5 -4 0 1 1 4 4
after sorting by abs
0 1 1 -4 4 4 -5
Max product of three is 4 * -5 * -4 * = 80
3 -2 -1 3 -1 4 4 -3
after sorting :
-3 -2 -1 -1 3 3 4 4
after sorting by abs
-1 -1 -2 -3 3 3 4 4
Max product of three is 4 * 4 * 3 * = 48
0 0 -2 -2 -2 2 -1 -2 3
after sorting :
-2 -2 -2 -2 -1 0 0 2 3
after sorting by abs
0 0 -1 -2 -2 -2 -2 2 3
Max product of three is 3 * -2 * -2 * = 12
-5 3 3 -5 1 3 -4 4 3 4
after sorting :
-5 -5 -4 1 3 3 3 3 4 4
after sorting by abs
1 3 3 3 3 -4 4 4 -5 -5
Max product of three is 4 * -5 * -5 * = 100
2 -3 -3 3 -3 3 4 -5 2 3 -4
after sorting :
-5 -4 -3 -3 -3 2 2 3 3 3 4
after sorting by abs
2 2 -3 -3 -3 3 3 3 -4 4 -5
Max product of three is 4 * -5 * -4 * = 80
0 3 1 -4 -3 -1 -3 0 3 1 -3 1
after sorting :
-4 -3 -3 -3 -1 0 0 1 1 1 3 3
after sorting by abs
0 0 -1 1 1 1 -3 -3 -3 3 3 -4
Max product of three is 3 * -4 * -3 * = 36
0 -2 4 -3 -1 1 -4 3 -3 -4 -4 4 2
after sorting :
-4 -4 -4 -3 -3 -2 -1 0 1 2 3 4 4
after sorting by abs
0 -1 1 -2 2 -3 -3 3 -4 -4 -4 4 4
Max product of three is 4 * -4 * -4 * = 64
1 -3 4 0 -3 -5 -5 -2 4 -4 3 -4 4 0
after sorting :
-5 -5 -4 -4 -3 -3 -2 0 0 1 3 4 4 4
after sorting by abs
0 0 1 -2 -3 -3 3 -4 -4 4 4 4 -5 -5
Max product of three is 4 * -5 * -5 * = 100
Press any key to continue . . .