Wednesday, April 28, 2010

Find three numbers in an array which forms a maximum product

This problem again is asked as a coding question in one of the top companies. I have provided the solution for this in C++.

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


Solution:
The program expects both the solutions, one in O(n) time and the other one in O(nlogn). To achieve O(nlogn), sort the entire set by using quick sort or merge sort and take the top three values.
I have provided the code for the O(n) case. It does a single scan on the entire set of elements once and finds the largest three numbers with the logic as shown below.

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman (My honorable room mate, college mate, work colleague)
// Version     : v1
// Copyright   : open
// Description : To find three largest numbers in an array in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main()
{
 int a[10] = {1,2,33,4,15,6,7,28,9,10};
 int largest_1 = 0, largest_2 = 0, largest_3 = 0;

 for(int i=0;i<10;i++)
 {
  if(a[i] > largest_3 && a[i] < largest_2)
  {
   largest_3 = a[i];
  }
  else if(a[i] > largest_2 && a[i] < largest_1)
  {
   largest_3 = largest_2;
   largest_2 = a[i];
  }
  else if(a[i] > largest_1)
  {
   largest_3 = largest_2;
   largest_2 = largest_1;
   largest_1 = a[i];
  }
 }
 cout << "largest :" << largest_1 << endl;
 cout << "2nd largest :" << largest_2 << endl;
 cout << "3rd largest :" << largest_3 << endl;
 return 0;
}

Cheers!!
Bragaadeesh

2 comments:

Anuj said...

What if you have negative numbers in the array?

b said...

@Anuj: I have already solved that scenario in a different post. Find it here