Tuesday 24 May 2016

Find the max product value of 3 numbers

Find the max product value of 3 number from the given array .
For example , if array has [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] find the max product from three numbers. max_product(x*x*x)

We need to consider following cases
a.   what if array has only -ves.
b.   what if array has only +ves.
c.    what if array has 0.
What if array has both +ves and -ves

Sort array, 
a.   Compute initial product has last three elements in the array.

b.   If array has more than 1 -ve values, take first 2 negatives and last positive compute product. If this product is greater than what we computed in step a, update maximum product.


import java.util.Arrays;
import java.util.Objects;

public class ArrayUtil {
 public static int maxProduct(int arr[]) {
  if (Objects.isNull(arr)) {
   throw new NullPointerException("Array shouldn't be null");
  }

  if (arr.length < 3) {
   throw new IllegalArgumentException(
     "Array should have atleast 3 elements");
  }

  Arrays.sort(arr);

  int length = arr.length;
  int maxProduct = arr[length - 1] * arr[length - 2] * arr[length - 3];

  if (arr[0] < 0 && arr[1] < 0) {
   int tmpProduct;

   if (arr[length - 1] >= 0) {
    tmpProduct = arr[0] * arr[1] * arr[length - 1];
   } else {
    tmpProduct = arr[length - 1] * arr[length - 2]
      * arr[length - 3];
   }

   if (maxProduct < tmpProduct)
    return tmpProduct;
  }

  return maxProduct;

 }
}


import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class ArrayUtilTest {

 @Test
 public void test() {
  int arr1[] = { -1, 2, 3, -4, -5, -2, -8, -4 };
  int arr2[] = { 1, -1, -2, 4, -5 };
  int arr3[] = { 3, 2, 0, 1, 4, 5 };
  int arr4[] = { 5, 4, 3, 0, -10, -20 };
  int arr5[] = { -5, -4, 1, 2, 3, 4, 5, 6, 7 };

  assertEquals(ArrayUtil.maxProduct(arr1), 120);
  assertEquals(ArrayUtil.maxProduct(arr2), 40);
  assertEquals(ArrayUtil.maxProduct(arr3), 60);
  assertEquals(ArrayUtil.maxProduct(arr4), 1000);
  assertEquals(ArrayUtil.maxProduct(arr5), 210);
 }
}



No comments:

Post a Comment