MaxProductOfThree - Codility - Solution

Java solution to Codility MaxProductOfThree problem (Lesson 6 – Sorting) which scored 100%. The problem is to find the maximum product of 3 numbers in a given sequence of numbers. The strategy is to sort list of integers and then find largest product by checking the 4 combinations of products.

The largest 3 elements product will be one of these 4 values, assuming we have an ordered list:

first 3 elements (highest values)
last 3 elements (lowest values – can have 2 large negative values that create a positive and then multipled by a positive)
first element and last 2 elements
first 2 elements and last element

First, add all the array elements into a list, order the list and then find the max of the above 4 values. It has to be a java.util.List and not a java.util.Set because duplicate elements ARE allowed.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package com.codility.lesson06.sorting;



import java.util.ArrayList;

import java.util.Collections;

import java.util.List;



public class MaxProductOfThree {

  public int solution(int[] A) {

    List aList = new ArrayList();

    for(int i=0; i<A.length; i++) {

      aList.add(A[i]);

    }

    Collections.sort(aList);

    

    int product1, product2, product3, product4 = 0;



    product1 = aList.get(0) * aList.get(1) * aList.get(2); //first 3 elements

    product2 = aList.get(aList.size()-3) * aList.get(aList.size()-2) * aList.get(aList.size()-1); //last 3 elements

    product3 = aList.get(0) * aList.get(1) * aList.get(aList.size()-1); //first 2 and last element

    product4 = aList.get(0) * aList.get(aList.size()-2) * aList.get(aList.size()-1); //first and last 2 elements



    int max1 = Math.max(product1, product2);

    int max2 = Math.max(product3, product4);

    

    return Math.max(max1, max2);

  }

}

TestNG test cases for this problem which all passed:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package test.com.codility.lesson06.sorting;



import org.testng.Assert;

import org.testng.annotations.BeforeTest;

import org.testng.annotations.DataProvider;

import org.testng.annotations.Test;



import com.codility.lesson06.sorting.MaxProductOfThree;



public class MaxProductOfThreeTests {

  private MaxProductOfThree solution;

  

  @BeforeTest

  public void setUp() {

    solution = new MaxProductOfThree();

  }



  @DataProvider(name = "test1")

  public Object [][] createData1() {

    return new Object [][] {

      new Object [] {  new int [] { -3, 1, 2, -2, 5, 6  }, 60 }, //2 * 5 * 60

      new Object [] {  new int [] { -3, 1, -100, 2, -2, 5, 6  }, 1800 }, //-100 * -3 * 6

      new Object [] {  new int [] { -3, 1, -100}, 300},

      new Object [] {  new int [] { -3, 1, 0, -100}, 300}, //-100 * -3 * 1

      new Object [] {  new int [] { -3, 1, 2, 0, -100}, 600},  //-100 * -3 * 2

      new Object [] {  new int [] { 10, 10, 10 }, 1000 },

    };

  }



  @Test(dataProvider = "test1")

  public void verifySolution(int[] pA, int pExpected) {   

    Assert.assertEquals(solution.solution(pA), pExpected);

  } 

}

MaxProductOfThree – Codility – Solution