Monday, May 3, 2010

Find three numbers in an array which forms a maximum product (for signed integers)

This is a problem that we had already seen. But it gives more kick if the input has negative elements and zero!!!

Question:
Given an array of integers (signed integers), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].
int[] MaxProduct(int[] input, int size)

The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product. Handling all these scenarios with comprehensive test cases, please find the code below for the problem implemented in C++

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman
// Version     : v2
// Copyright   : open
// Description : To find three signed numbers in an array with max product
//========================================================a====================

#include <iostream>
using namespace std;

#define MAX 10

int* MaxProduct(const int input[], const int size)
{
 int* output = new int[3];
 int negative = 0;
 for(int i = 0; i < 3; i++)
 {
  output[i] = -999999;
 }
 int min[2] = {0,0};

 for(int i=0;i<size;i++)
 {
  // find two smallest negative numbers
  if(input[i] <= 0)
  {
   if(input[i] < min[0])
   {
    min[1] = min[0];
    min[0] = input[i];
   }
   else if(input[i] < min[1])
   {
    min[1] = input[i];
   }
   negative++;
  }

  // find three largest positive numbers
  if(input[i] > output[0])
  {
   output[2] = output[1];
   output[1] = output[0];
   output[0] = input[i];
  }
  else if(input[i] > output[1])
  {
   output[2] = output[1];
   output[1] = input[i];
  }
  else if(input[i] > output[2])
  {
   output[2] = input[i];
  }
 }

 if(size != negative)
 {
  if((min[0] * min[1]) > (output[0] * output[1]) || (min[0] * min[1]) > (output[1] * output[2]))
  {
   output[1] = min[0];
   output[2] = min[1];
  }
 }

 return output;
}

int main()
{
 const int input[MAX] = {-6,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result = 0;
 result = MaxProduct(input,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result[i] << endl;
 }

 const int input1[MAX] = {0,-1,-2,-33,4,15,-7,-28,-9,-10};
 int* result1 = 0;
 result1 = MaxProduct(input1,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result1[i] << endl;
 }

 const int input2[MAX] = {0,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result2 = 0;
 result2 = MaxProduct(input2,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result2[i] << endl;
 }

 const int input3[MAX] = {6,1,2,33,4,15,7,28,9,10};
 int* result3 = 0;
 result3 = MaxProduct(input3,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result3[i] << endl;
 }

 return 0;
}

Cheers!
Bragaadeesh.

4 comments:

Sreekanth said...

Hi Brgadeesh i can we can use this algo its simple
static int getMaxProduct(int x[]){
int answer = 0;
Arrays.sort(x);
if(x[x.length-1]>0){
answer = (x[x.length-1]*x[x.length-2]*x[x.length-3] > x[x.length-1]*x[0]*x[1])?x[x.length-1]*x[x.length-2]*x[x.length-3]:x[x.length-1]*x[0]*x[1];
}else{
answer = x[x.length-1]*x[x.length-2]*x[x.length-3];
}

return answer;
}

Bragaadeesh said...

@Sreekanth: Thanks for reading and replying. Although your solution is right in all ways, the speed of it is O(nlogn). The simple reason being the Arrays.sort(x). Just because a program has more lines of code does not mean that its not fast.

Arrays.sort(x) does a quick sort within which is going to scale or increase nlogn times for each n. Whereas the solution that I've provided does the job in O(5n) = O(n) time. You can try it yourself for a huge data set.

Thanks,
Bragaadeesh

Sreekanth said...

HI Bragadeesh ,
Thank you very much for your reply . You r ryt. YOur solution is clean ! with O(n) time .To be clear i did not mention that your lines of code takes time . i just said it was simple .

CJ said...

thank you very much for your contribution. just a little problem, I think there might be a memory leak. testing with valgrind, whenever you allocate on heap with 'new', program is responsible to delete that after using.