CODILITY - LESSON 4 - MaxProductOfThree

PROBLEM (codility.com - click here to see)

A non-empty zero-indexed array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6

contains the following example triplets:

• (0, 1, 2), product is −3 * 1 * 2 = −6
• (1, 2, 4), product is 1 * 2 * 5 = 10
• (2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

MY SOLUTION (100% score, time complexity O(N * log(N)))

class Solution { public int solution(int[] A) { Array.Sort (A); int a=0; if (A[0]<0 && A[1] <0) a = A[0]*A[1]*A[A.Length-1]; int b = A[A.Length-1]*A[A.Length-2]*A[A.Length-3]; if (a >b && (A[0]<0 && A[1] <0)) return a; else return b; } }

It first sorts the array (from min element to max element).

(Array.Sort (A) => -3,-2,1,2,5,6)

There is two possibilities:

• The first two elements are negative. Then we need to check if the triplet of those two elements and the last element in the array is > the product of the last three elements.
• Any other situation, the maximal product is the product of the last three elements.

PR

codility.com - result