Product Maximization Problem in Java

There is one of two questions I have face in the Hackathon Delhi in the amazon hiring process.

Problem:

Given an array of integers, which can contain both +ve and -ve numbers, you have to maximize the product of any 3 elements of the array and print that out.

The elements can be non- contiguous. If size of array is less than 3 then answer will be 0.

Input:
Input will consist of two lines. First line will consist of n i.e, size of array. Next line will contain comma separated numbers.

Constraints:
0≤n≤10000

−1290≤A[i]≤1290

Note: Input will always have exact 2 lines. And all correct integers will be provided which will not generate any parse exception. The second line will always have correct number of elements, the count of which is given in first line.

Output:
Print the maximum product. Don't print the elements.

SAMPLE INPUT
6
-5 -7 4 2 1 9

SAMPLE OUTPUT
315


Explanation
Maximum product is -5 * -7 *9 = 315

Another case:
Input array: 4,5,-19,3
Maximum product is 3 * 4 * 5 = 60

Solution:

package com.dineshonjava.algo;

import java.util.Arrays;
import java.util.Scanner;

public class ProductMaximization {

 private static Scanner sc;

 public static void main(String[] args) {
  sc = new Scanner(System.in);
  int n = sc.nextInt();
  int [] arr = new int [n];
  for(int i = 0; i < n ; i++){
   arr [i] = sc.nextInt();
  }
  productMaximize(n, arr);
 }

 private static void productMaximize(int n, int[] arr) {
  if(n < 3){
   System.out.println(0);
  }else{
   Arrays.sort(arr);
   int max = 0;
   if(arr[0] < 0 && arr[1] < 0){
    if(Math.abs(arr[0]) >= arr[n-1] || Math.abs(arr[0]) >= arr[n-2]){
     max = arr[0]*arr[1]*arr[n-1];
    }else{
     max = arr[n-3]*arr[n-2]*arr[n-1];
    }
   }else{
    max = arr[n-3]*arr[n-2]*arr[n-1];
   }
   System.out.println(max);
  }
 }
}

This program may not be solve all test cases but I have run 10-12 test cases which is running fine. So please suggest anyone if you have another better way to solve this problem.





No comments:

Post a Comment