CODILITY - LESSON 4 - Triangle

PROBLEM :

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

For example, consider array A such that:

  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 20

Triplet (0, 2, 4) is triangular.

GOOD SOLUTION (93% score, time complexity O(N*log(N))

(codility.com click here to see breakdown of the test results)

class Solution { public int solution(int[] A) {  

Array.Sort(A); if (A.Length <3) return 0; for (int i=0 ; i<A.Length-2 ; i++) { if (A[i] + A[i+1] > A[i+2] ) {return 1; break; } } return 0; } }

I made one mistake here which I realised only once all the test results were ran: I didn't account if the triplet is formed by 3 maxValue integers (C# will wraparound the result of the sum of two maxValues).

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

(codility.com click here to see breakdown of the test results)

class Solution { public int solution(int[] A) { Array.Sort(A); if (A.Length <3) return 0; for (int i=0 ; i<A.Length-2 ; i++) { if (A[i] + A[i+1] > A[i+2] ) {

return 1; break; } if (A[i] == A[i+2] && 

A[i+2] == A[i+1] && 

A[i] == Int32.MaxValue) {

return 1; break; } } return 0; } }

PR

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